We started changing products from "Product is virtual, skip shipping" to requiring an address a while ago because when customers were checking out there was often no address on the PayPal section of the order page and after getting hit by a scammer we were checking IPs on Maxmind and comparing the locations. We now seem to be receiving the checkout error emails more frequently with:
"10736
Shipping Address Invalid City State Postal Code
A match of the Shipping Address City, State, and Postal Code failed."

A customer tried to edit his address about 20 times before he finally gave up and made a PayPal account because he was determined to place an order. He attached the card he was trying to use, with the same details and it worked.

Is this error commonly caused by PayPal not liking how Zen Cart handles the address or is the problem solely with PayPal? I was really confused that he was able to use his card on a new PayPal account but it was being rejected without an account, same address.