I think the best solution is to pass the shopping cart ID or session id to paypal as the invoice ID. Paypal has a built in protection to prevent the same invoice ID from being charged twice. That way you won't have to worry about duplicate transactions.
I suspect the error may have been on their side, so there might not be anything you can do about it and it might just stop happening since they have likely resolved it. I haven't found any information about that particular error in my searches.