I have a strange problem sending SMS's from Cingular to Verizon.

Because of international travel, all my contact phone numbers are in the following format:

+1 (555) 987-6543

If I try to send an SMS to a friend by looking them up via, say, their last name, the above-referenced number appears. However, upon sending the message, the Verizon receipient never receives it.

If I try to enter the phone number without the pluses or parantheses, the Treo instantly matches it to a contact entry, and automatically reinserts the pluses and paranthases. So again, Verizon doesn't receive the SMS.

HOWEVER, if a friend from Verizon SMS's me, I get the message just fine. I can ever reply to the message without any problem, because when you reply to the message, the TREO simply replies to the number it received, without screwing up the fomatting. Hence , it replies to the phone number 15559876543.

So, does that mean that the only way to send an SMS to someone at Verizon is to either:

1) NOT use number formatting in the phonebook, or
2) NOT have a receipent's mobile number in the phonebook (so it doesn't get automaticallty formatting in the SMS app), or alternatively,
3) Force the receipient to send an SMS to me first and them simply reply to it to avoid the Treo from automatically formatting the number?

So far, this problem only appears to occur with Verizon.

Anyone have any ideas?