I've been very happy over the last 5-6 years with easydns.com.

And I'm firmly in the 'don't register where you host' camp. If you ever have a hassle with your webhost, you don't want them having any control at all over your domains. No fine print, no hassles. In fact, my registrar doesn't even offer hosting.