I'm having the same issue. From verizon side, it's recorded that the msg are sent out but not received at the other end. Nor I can receive the msg they sent. But with different country, the msg I sent was received, but I can't received the reply msg.
I am having the same problem on my droid. Verizon Wireless trying to text a friend in Peru but the text message never gets to them. The Verizon Wireless website records that I've sent the message. Using the Google Voice app (working) for now. Didn't have a problem with the MyTouch (T-Mobile) so I'm guessing it is either Android 2.0 (notice it automatically adds 011+) or Verizon Wireless. Yes, I activated international dialing.