I've used whois protection services for years (and for thousands of domains), there's never been a problem for me.

When the whois protection service is provided by the registrar you used to register the domain, how is that third party ownership? They already have a lot of control over the domain.

I don't know about ICANN rules on the matter, however I think they would have pressured registrars to stop offering such services, if that was the case.

If you have further information/links on the subject, please elaborate.