Most registrars that offer "free" whois privacy, it's only for the first year. Simple solution - transfer the name to another registrar in about 11 months who offers free year of privacy on transfers.
GoDaddy has alot of issues, their SOPA waffle is just the latest (and a *huge* one), but over-pricing name registrations isn't really one of their issues. In fact cheap name reg's is one of the key ways they grew and continue to grow. If you reg or transfer 6+ names with them you get a year of free privacy on those names.
internetbs gives you free privacy for the lifetime of your name's registration there, I think they are the only big player that does that. And with name registrars I don't recommend dicking around with unknowns or newbie operations - ICANN accreditation is meaningless, and names are too valuable to trust in the hands of shady companies. internetbs has been in bus for quite awhile (in internet time) and yes they are offshore and they provide great support when needed.
I've had good experiences with others, including namecheap. Don't really have a strong opinion on netfirms, don't care for dot tk because from what I know they have some bad policies in place that could get your name blacklisted or repo'ed.
Just don't use 1&1 for anything...no matter how tempting...ever.