mhansen - 7:41 pm on Jul 25, 2011 (gmt 0)
We have had a PO box ($40/year) for several years, and with Google Places, you can setup your business as a "Service" based company that operates in a service area versus your office address.
Also, there are remotely located PO box services you can use if you prefer complete anonymity, but that also comes at the expense of authority and trust. Just like local signals helping your local results, trust signals (phone, address, ssl, transparency) will help as well.
Yes... its an added expense, but in general... if a business cannot account for a $40-$50/year expense, its got bigger issues than just Google.