I'm on T-Mobile UK too. When I was in Tenerife I couldn't connect to any network (stock PR1.3, UK firmware). I used Wi-Fi plus Skype Out as a work-around. I got someone in the UK to contact T-Mobile for me and they seemed to think that it should just work. There was no mention of needing a deposit.

I would try flashing the global FIASCO image to see if that makes a difference.