I have added the session_regenerate_id() code to your checkout success page. This should force the id to be regenerated as a new unique id. If the problem is that the same session id is being used for more than one transaction then this should resolve the problem.
While you test this part out please do the following.
Start all of your testing in a new browser session, make sure to delete cookies and so forth so that it is a clean test.
When you get to the confirm page view the source and look for this element:
<input type="hidden" name="invoice" id="invoice"
When you find it in the source copy the value of this element and paste into in a text file for safe keeping.
Now confirm the purchase and transact the order on PayPal, when you get to the checkout success page it should display some similar info as before but also the new session id after the session is destroyed.
Record the session id that you see here after the session is destroyed and put it in your text file to compare to the id that was submitted with the order.
Now perform your test again and record the values once more. The id's should be different every time you go through, if they are not then you will get this error about the duplicate invoice. Please post back with the text file and the id's you recorded, make sure to label them so we can see when you got certain values.