Scott,
Yes, you're right. The P.O. box causes a lot of hassles. I know bcause I'm in the same situation. Here's one thing that can be done: Register your street address along with your P.O. box on your credit card. Always use BOTH whenever you have to give your address.
Tom G.