Most likely it's a result of the customer truly entering a bad postal address. PayPal does some address validation before accepting an order.
Do you have the details of the address info they entered?