Even if you paid for a domain, you would have to give your address and phone number, and other data. It's called the Whois database. (
http://whois.domaintools.com/)
The one difference, however, is that if you bought your domain, most sites allow you to buy an upgrade (not much) to have your Whois hidden. Most paid hosting companies give you Whois Protection for free, as well. However, you still have to give the company your address, it's just that the average guy can't get it. Only the police can, in case your doing something illegal.
Note: If your buying a domain, use NameCheap. Not only do they have the cheapest domains that I've seen, they have a coupon that lowers the price by 88 cents at all time (it changes every month), and they offer FREE Whois protection. I bought a domain from their once, it was awesome.
IPost2Host used to be a GREAT service in which you did forum posts to get free domain names, and hosting. Even provided Whois protect! Unfortunately they didn't make as much money from ads as they lost from giving away free hosting and domains... so they got shut down.
Bottom line: Don't get worried about giving away your name/address to these companies.