I've been using my local USPS PO box for domain registration for the past few years. It pays for itself when you figure in the cost of add-on services from registrars. I also use it as an address for similar in-person sign up forms also. Aliasing services like Fastmail are also a solid part of the equation. Use it as much and in as many places as possible. You could also try an IRL alias-type hack by giving out a slightly different name (middle name, title, etc.) when filling out your address.
