I've just handled this exact situation by combining both the Google Places (new) API, and the Google Address Validation API.

The Address Validation API handles PO Boxes (at least in the US.) So, I simultaneously do a Places request to get partial, autocomplete matches and an Address Validation request to check for exact matches. Usually a PO box with a zip code is enough to get an exact match.