use a PO box? unless there are some downsides, like ssl cert issuers not issuing for PO box?

this looks easy enough: https://poboxes.usps.com/poboxonline/search/landingPage.do

I'd assume other countries provide something similar?

PO boxes are not a legitimate solution for someone needing total anonymity. Anyone can fill out a request for boxholder information form to find out the identity of the person who registered it.

edit: The USPS will provide this info no questions asked, no subpoena or court order required.

Don't use domain privacy. By using it you give up legal ownership of your domain. The entity listed in WHOIS legally owns the domain.