I've gotten two of those, one for each of (only) two domains I own, both on the same day. They grab this info using the WHOIS information. It sucketh verily.

One thing you could try is Domains By Proxy. It is an offshoot of GoDaddy that puts anonymous information in the WHOIS fields. It costs about $10 on top of the registration fee ($8), so you get privacy for about the same cost as a domain from elsewhere. Give it a shot!

Damien