I have been with Godaddy for a long time (before I moved away and got on the train again). It's ugly and a shitty organisation but it just works and is rather cheap.
I have some domains hosted with mediatemple since they had a great 5£/com offer not long ago.
There are a few others out there that I hear often like
namecheap
gandi
hover
On this topic it's really interesting to read http://www.marco.org/2011/04/14/why-is-it-so-hard-to-be-a-go...
I guess I could go on and on with the list, but the only thing I can not do so far: give a surefire, perfect and reliable solution. I guess it also comes down to personal preference in the end.