PayPal Checkout Errors Increased Since Requiring Address

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.

I've been having terrible problems with 10736 errors, for a long time. I can't help you with your question, but when you asked about "required" address, I changed the settings in PayPal module so address is not required... and I haven't had those 10736 errors since. At this point it's a relief. I hope I've found the magic Setup combination so it doesn't happen anymore.

We have another Zen Cart shop that's using a much older version (v1.3.9h) and we don't get this 10736 error on that website. Just the one that's running the latest version of ZC.