Ditto what Chris says.
Be
very careful who you search for names through. Even huge,
supposedly reputable (ha!) outfits like Verisign/Network Solutions will lock up a domain name after someone searches and finds an unused name through their domain name search. Verisign
claim they only do it to protect their customers. (Yah, sure. Wanna buy a bridge to nowhere?)
I use 123CheapDomains.com myself, though they're not all
that cheap at about $14/yr -- but they have very good, one-on-one service and have been very helpful to me in the past. And you do have to put up with seeing their name as registrar if you do a WHOIS on your own site...
But they don't pull sleazy crap like Verisign or some of the other losers out there. (At least not in my experience. You never step into the same internet twice.)