Yes, if you go through the Places help, in one spot it does say that no P.O. boxes are allowed; but in another spot states that all you need to verified on Places is an address where they can mail you a confirmation code; after which you can hide the address and define a service area instead. So really, any mail box service other than the government Post Office will do for getting that code; you just need to put "Suite #", Office #", etc. in front of your box number, and then it shouldn't raise flags.
And I'm sure there are many with which you don't even have to use a box number. I am Canadian, but live right on the US border. In the small border town on the US side is a parcel receiving service I use, set up for Canadians to order from the many US companies that won't ship to Canada. We aren't assigned box numbers there, I just have parcels addressed as My Name, 123 Main St. Sumas, Wa. In the modern computer age it is a much more efficient use of space for them to put my name and the shelf spot they found for it in the computer when they receive a package, and then look up the shelf location when I get there. They have been doing so well with the business that 3 new competitors have opened up the past 2 years, all of which don't need box numbers. I know several people that get regular mail through them; a US magazine subscription is 1/4 the cost of what it is up here. These people used to keep P.O. boxes at the Sumas Post Office, but the private businesses charge half as much.
@Gmaps9 - Here is the
official guidelines/policy. P.O. boxes not being acceptable is also in
this page's best practices. A Google mod has included non government postal centres into the policy
here.
How's this for a thought; Google could use us for our local knowledge; provide us a method of flagging any address that provides mailing address services. Not only could it help with Map Maker, but this could go into the database that's used for checking Places addresses. It would best to be set up as something that requires RER or GR review on any edit to remove the flag.