I have discovered this problem with my store today. It is a new problem as I regularly receive orders without customers first registering an account on the site. I have not customised my site recently.

Customer has not registered an account and selects the Paypal Express button. They are redirected to Paypal and when returned to the site to confirm receive this message
"We are sorry for the inconvenience; however, at the present time we are unable to use PayPal to process orders from the geographic region you selected as your PayPal address. Please continue using normal checkout and select from the available payment methods to complete your order."

The following were confirmed working as normal.
Customer has registered an account, is logged in and checks out using the normal cart method the sale completes as expected.
Customer has registered an account, is logged in and selects the Paypal Express button the sale completes as expected.

I have Zone shipping set to only ship to UK (Zone 1) - I have "Request International Quote" mod installed for international enquiries.
I have tested with "Express Checkout: Automatic Account Creation" set to both YES and NO with the same result.

v1.39h Fresh install via my host eukhost
PayPal Express Checkout
Request International Shipping Quote Only

I've read some of the older threads with similar issues but none seem to have the same problem with only a non registered customer using Paypal Express.

Any help would be very much appreciated.