In the past I have primarily used Dotster, and not only have I gotten spam after registering domain names but junk faxes too (I no longer list the fax number on domain registrations because of this). I don't think it has anything to do with Dotster though, I think the spam is coming from third parties who are going through the domain registry harvesting e-mail address, postal addresses, and everything else.
I never wanted to use GoDaddy for domain registrations because they say flat out in their registration agreement that they may sell your information in bulk. But the more I think about it, the more I realize that if you get a domain name you're going to get spammed no matter what you do.
MasterMindz: You use Network Solutions?

Seriously?