First things that come to mind are:
1) For the “external” TFTP/SIP providers, do you have the DHCP option 150 pointing to those IP addresses? I read that you changed remote IP/NAT, but I’m asking if the DHCP server your phone is connecting to is pointing it to the “remote” locations properly…
2) When you said it is working when you keep the TFTP/SIP internal, it works fine. What is running these services? Are you connecting you phones to a CME/CM solution? or are you running and asterisk/hybrid setup?
More info about your topology and services would make assisting you a bit easier