I normally use DirectNic and thier pro-dns service, in ten years they've only ever had one outage and that was when they upgraded. A bit dearer but I like it.
I do know what you mean about Godaddy though, well impressed but heard bad things a few years ago about thier reliability, nothing since then so you never know they might have thier act together now
