I believe I have found a solution to this problem.
I had a similar issue. I work in Azerbaijan, but keep my US Verizon Samsung Note 3 and swap SIM cards when I travel. I too was having the issue of not having my outbound text messages received, unless I removed the country code and prefix. However, as this is how my contacts were stored and how the inbound call-ID labelled them, this was very frustrating and time-consuming.
In the end, the solution is to utilize the Assisted dialing feature, with some modifications (phone dialer>settings button>call settings>assisted dialing [tap to edit]). When I chose the country for the assisted dialing, it correctly selected my country code as 994. However, in order to make my texts work I had to manually add in the "+" sign. now the phone recognizes the "+994" that is in all of the contacts and inbound phone numbers. texts now seem to works as they should. Also, be sure to turn the assisted dialing on.
Hope this helps all of the other travelers out there.
-Alex