Surely there are reliable hosts that offer free privacy protection, but usually for the first month or something. (Think GoDaddy had such an offer, correct me if I'm wrong.)
On the other side, beware of anything that sounds too good to be true. Usually, it really is too good to be true.