Also:

- is your PayPal account "Verified" ?
- please confirm whether you are using a "Personal" or "Premium" or "Business" account.

- was the customer accessing PayPal as a result of choosing the "PayPal IPN" option on the checkout_payment page ? or were they specifically using Express Checkout ?
- "when" did they get this error message ?

- can it be easily reproduced on demand ?

- can we locate a customer willing to help test (and of course be refunded for test purchases)?