I also have a T-Mobile pre-paid mobile phone. Thankfully, the only spam I got was from T-Mobile itself (win, win, win, big prices!) and Club Nokia (you really still have a 8110? no, I've even switched to Sony/Ericsson).

When I called T-Online to stop spamming me, the Agent first told me: Yeah, no problem. Give me your password. I gave her my password. She told me: Oh, you have a pre-paid mobile phone. Cannot stop those messages. I've asked her again and all of the sudden it went ok.

She seemed a bit angry with me for some reason though. Later, I didn't receive any spam any longer...