I just had a customer with this same issue.

"Unable to process payment. Please contact the merchant as the shipping address provided by the merchant is invalid, and the merchant has requested that your order must be shipped to that address."

However he says he's entering the same address that PayPal has on file.

I unchecked the "submit address information to override.." checkbox to see if this will help. But since I'm in the US, will this have any effect (negative?) on our regular domestic customers? I'm pretty sure this guy is not international, either.

Thanks for any advice you can give