You don't have to use your registrar for DNS hosting. You don't have to change registrars to have somebody else provide DNS service for your domains, either. Check out easyDNS, for example.
I presently have my personal domains registered with GoDaddy. I find their ads in very poor taste, and they're always trying to upsell you to stuff you probably don't need or want, but they haven't annoyed me enough to go through the hassle of switching registrars. Yet. I do use their DNS hosting service, and it does allow TXT records. I haven't personally noticed any problems with their hosting service, but I've got a friend that has complained about vanishing MX records in the past. He swears by easyDNS for anything that needs to be truly reliable. I do use easyDNS for one domain that I manage for somebody else that uses a foreign registrar (ccTLD). The additional expense kind of sucks, but I don't trust the registrar for that domain. I've set up TXT records with easyDNS, so I know that works. They've got explicit SPF support in their interface, which is what I use TXT records for.
You could do worse than GoDaddy, so you should probably check them out if you can stomach navigating their website.
easyDNS is also a registrar, though they're not cheap (as compared to GoDaddy, at least).
Everybody I know is using either GoDaddy or easyDNS at the moment.
Update
The GoDaddy SOPA fiasco finally motivated me to go through the hassle of migrating. I've transferred domains I've registered to Namecheap. I haven't tried their DNS service, I'm using Rackspace Cloud DNS.
I also eventually experienced the "MIA MX record" problem myself. They were there in the management interface, but not showing up via dig. I didn't try contacting GoDaddy support, I manged to clear the problem up by vaporizing all the records and reloading them.
