We use [url=http://www.bulkregister.com]Bulkregister.com[/url]. They charge a $79 membership fee but registrations are only $10 for the time being. They usually use a sliding scale based on the number of registrations but they are having a special now. It is very easy to register high volumes of domains.
[url=http://alldns.com/]alldns.com[/url] They are dirt cheap - $12.75 a domain. I never used them, but have read complaints in newsgroups about customer service. Then again what do you want for 13 bucks?
Most of the cheep domain registrars are resellers for OpenSRS http://www.opensrs.com/ if you register a lot of domains (25 month or so) It would make sense to become a registrar yourself. Just a few scripts to set up and you have to buy domains in blocks of 25 or more. $10.00 a domain