trig42: I have just had a similiar situation.
I have a client who had two domains hosted with Xtra (a .com and a They were using Officemail.
Right from the start we had decided to transfer their domains to another host (just so that then we could have easy access to their zone records).
Xtra/Telecom were actually really helpful, and the domain transferred overnight and they removed their DNS records the next day and mail flowed right from the time the server got on the internet.
The .com one was a pain though as the contact details in the domain were out of date and they had nowhere to send the code to change it to another provider (not UDAI, but some other bunch of letters). There again Telecom were as helpful as they could be, and we eventually got the code, then it took out hosting provider a week to change it over (apparently common for .coms?).

For some reason, some of the .com emails from their clients are still pointing to xtra (and therefore getting bounced), it looks as if the sending servers had not updated their DNS (so the 7 day TTL probably). It is all settling down now, but overall I found Telecom/Xtra to be quite helpful. The people I spoke to there were on to it and had no problems helping me (I needed a PTR created for their static IP and the first guy I spoke to had that done in about a minute).

Don't telecom now subcontract out their domain names to Domainz? I remember reading that somewhere.
With .coms, they can be a pain to transfer and it can take days. You need an authorisation code, and the domain unlocking for it to be transferred. I presume you also need to make sure that telecom removes all the records on their system, otherwise people who are using telecoms network may have trouble accessing the domain and sending emails to it.