Magento Paypall @ 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

We've fixed this Magento/PayPal issue for quite a few clients when they were told the same thing by PayPal support. 

In Magento Community 1.7.0.2 you need to copy the file: 
/app/code/core/Mage/Paypal/Model/Api/standard.php 

to: 
/app/code/local/Mage/Paypal/Model/Api/standard.php 

and change line 238 from: 
$request['address_override'] = 1; 

to: 
$request['address_override'] = 0; 

Once you do the issue goes away and you won't experience the issue with orders anymore. It would be nice if this could be a config choice in future versions of magento, or change to paypal's recommended setting by default. 

Some of our Magento clients receive the same error as your clients were on up to 1/3rd of their PayPal based orders.