I too am on T-Mobile US and I had the same problem, I had some success when I switched from IP to IPv6 in MMS settings, plus the same APN settings as paulwk. But it seems the problem can come back, even with IPv6, if you get a 'mms-engine' process stuck in memory like I did.
Under normal operation that process should exist only as long as it takes to send an MMS message. When things were bad I even killed the mms-engine process in a terminal and it respawned, preventing MMS from working (perhaps it respawned because the Messages app was still trying to use it?). If I insure there are no mms-engine processes running though, I can send and receive MMS. I even slept the device and MMS works, and also rebooted and MMS works.
So if your MMS capability breaks, close your Messages app, try 'ps ax |grep mms-engine' and kill off that process before trying again, with 'kill <PID>' or maybe just 'killall mms-engine'. deprecated, would you concur with this theory?
