This is awesome. Keep it going guys! Good thing we didn't stopped due to some negative comments from guys with points. Just repeating roman.dor post to help spread the steps to solution:
"- send an email to the above recipients explaining the problem, that you bought an iPhone for the full price of 649$ + taxes (for the 16GB model), and that you specifically asked for it to be used in another country with another carrier;
- write that after you got in your home country you have the SMS problem;
- thus no iMessange and no FaceTime (I think this is the catch, as these are their most mediate features);
- provide them all the details about the phone: Model, Serial Number, IMEI, MEID, your phone number (at which you can be contacted);
- tell them that the email address with which the iPhone is associated in iTunes;
- try to send the email from the email address with which the iPhone is associated;
- if you can attach also a photo of the receipt, that would be great (I did that), the receipt has the Model and the
Serial number of the phone, so you are very credibile in this;
- if you can provide also the name of the store where it was bought (it's written on the receipt).
After the mail with the above details I got contacted the second day and the third day the problem was solved ;)
So after all it's a lock/unlock problem!
Wish you all to solve your SMS problem too!"