I had a similar problem while testing in the PayPal Sandbox, I kept getting the "invoice has already been paid" message.

This is one of the more obvious solutions that worked for me: When setting up the correct PayPal e-mail address in Administer/Store Administration/Configuration/Payment Settings/Payment Methods, you need to provide the Sandbox business email, NOT the email you would use to login to your Sandbox account.

It took me several attempts to figure out the error I had made, hopefully this will help others that plan to test payments via Sandbox.

Z