Wow. DNS server providers don't really have a lot of work to do, other than keeping their servers running. They shouldn't be dropping or mixing up records.
We use the free service from Zoneedt.com for some of our domains and have had ZERO complaints with their service. There was a single day of a DDOS attack on a couple of their servers, but they took care of it quickly, gave us a free THIRD server, and answered all of our questions promptly. All for FREE.
Or, switch your domain registrar to Godaddy.com. They provide free DNS services now, with full control, for all domains registered with them.
Hmmm...I just saw the date on the original post. Why are we answering this question? Obviously, the original poster is long gone!