This is a common problem with many merchant gateways that use address validation for eCommerce transactions.  This is because this is the only case where the number wouldn't come first before the street name. 

If you reverse the format of the address line (e.g., enter in the address 1234 P.O. Box rather than P.O. Box 1234), you should be able to resolve the problem.