I had a similar problem with one of my blackberries.
I had an "unlocked" device from a users that was on TMO. Since it was unlocked I could use it on Cingular. I signed up for the data plan etc.
A Few months later I started having problems and it stopped sending me my email all together. voice communication was just fine.
When I called Cingular CS they passed it over to the next few levels of customer support for the blackberries.
Cingular couldnt figure it out and went to RIM, who told them that the device was originally registered to TMO and that the message problems were coming from TMO as the PIN was still "active" with them.
Cingular then contacted TMO directly about this PIN# and got me on a confernece call to explain why I wasnt getting my email, even though I had my web account (BIS) on Cingular.
In short they (TMO) would not release the device PIN even though the device was "unlocked" and since data was coming through thier servers without a data plan they blocked the device, so I was out of luck.
Now, I'm no expert on the back end of how things are supposed to function with the messaging but thats what happened to me..... I was out of luck
Since that time however I have had other units and have never had problems with them (most of them are unlocked devices from TMO!!)
Regards,
Dave