PayPal gateway has rejected request. Payment has already been made for this InvoiceID

There are few scenarios in which you can work out this issue which is returned in PayPal response.

Before doing this changes understand and know your Magento websites, PayPal settings and Magento Instances (dev, staging, production).

1. Test orders, again and again, posting to Paypal after cleaning orders database tables, so maybe it is sending old invoices. Can add some prefix in an invoice.

Check here - https://www.warpconduit.net/2012/04/18/how-to-change-the-order-increment-id-and-prefix-in-magento/

2. Can create some test orders via admin so Magento will send another invoice or order to PayPal, But make sure to create admin orders after adding any prefix value.

3. PayPal account settings: Only if you are using same PayPal account for multiple websites or else you have more than one instance of Magento of same website.

PayPal providing feature that whether to block or to allow invoice ID.

Logged in Standard PayPal Account > Profile > Payment Receiving Preferences: On this page you will find "Block accidental payments" set "Allow multiple payments per invoice ID".

So one of the tips will get resolve PayPal duplicate invoice Id issue.

By default, magento set the paypal invoice number (INVNUM) equal to the order increment id. This is a good practice because it allows you to have a one to one mapping between your order and the transaction.

You may get this error message if you or your teammates have sent the same invoice number to paypal before using the same paypal sandbox account. I would suggest you to add the hostname and username as the prefix of the invoice number and add the timestamp as suffix, so that the invoice number will always be unique when you are testing your checkout process. For paypal express checkout, I added the following codes right before if it sends the request in the callSetExpressCheckout method in app/code/community/Mage/Paypal/Model/Api/Nvp.php:

// if it's in the testing mode, add a prefix to avoid duplicates
if (Mage::getStoreConfig('paypal/wpp/sandbox_flag')) {
    $processUser = posix_getpwuid(posix_geteuid());
    $request["INVNUM"] = gethostname().'-'.$processUser['name'].'-'.$request['INVNUM'].'-'.time();
}

If you are using sandbox mode, Then delete the all orders refresh the cache problem will solve. Simple!

Have you recently switched servers or is this on a development server?

You may have to change your increment_id.

https://www.warpconduit.net/2012/04/18/how-to-change-the-order-increment-id-and-prefix-in-magento/