i recall about a year ago, fury or someone telling me that OT uses www.dotster.com . it's not super cheap (i pay $14.95 or something like that, per year) but i find it to be really good
I'm with AWRegistry which isn't cheap either ($35/yr) but very good service. I've heard many success stories from godaddy.com as well.
Something else to think about on the cheap ones is to determine whether you are buying or renting the domain. Sometimes it isn't outright clear what they do. I've seen businesses advertise low-low costs but if you read the fine print you find out you are actually paying someone else to buy it for you. They hold ownership of your domain. Most of the big-names do sell the domains (not rent) though, so staying mainstream is the way to go.
I musta missed this thread earlier.
I can get the registeration setup if you host with me.
Just to register for later hosting I recomend dotearth .
They aren't the cheapest, but They are very good.
You've got to watchout for some of these Real cheap places.
Don't use RegisterFly. They are crap.
I thought they were all the same, until I got stung by them.