Swedish company PRQ offers anonymous domain registration for $40/year. I used to have one domain registered with them to blog safely and anonymously under a pen name.
They're the company who hosted The Pirate Bay and Wikileaks websites, and have a good track record of not interfering or giving out customer data unless what you're doing contravenes Swedish law, which makes domains and sites hosted with them somewhat resilient to take down orders.