CAUSE OF THE PROBLEM:
The presented solution are only workarounds for the underlying problem which is that the increment_last_id for invoices is lagging behind the increment_last_id for orders.
There is nothing wrong with the Magento code, it is the Database that is in a problematic state. This usually happens after a Magento update.
To fix the problem you just have to set your invoice increment_last_id to the same value as the order one.
UPDATE
As pointed out by others, it is normal that these ids are not in sync, but if the invoice id is too much BEHIND the order id (and not the other way around) problems with PayPal can occur (more information here). Before turning down this solution, just try it out, it worked perfectly for me and others.
HOW TO FIX:
Use your preferred DB management tool (PHPmyAdmin, Adminer, ...) go to the eav_entity_storetable and check the values. It should look sth. like this:
+-----------------+----------------+----------+------------------+-------------------+
| entity_store_id | entity_type_id | store_id | increment_prefix | increment_last_id |
+-----------------+----------------+----------+------------------+-------------------+
| 1 | 5 | 1 | 1 | 100001708 |
| 2 | 6 | 1 | 1 | 100000926 |
| 3 | 8 | 1 | 1 | 100000888 |
| 4 | 7 | 1 | 1 | 100000054 |
+-----------------+----------------+----------+------------------+-------------------+
The interesting values here are:
- ORDER increment_last_id: entity_type_id = 5 (100001708)
- INVOICE increment_last_id: entity_type_id = 6 (100000926)
So the only thing we have to do here is set the INVOICE value to the one of the ORDER value. We can do this with any db management tool, or directly with the sql command
UPDATE eav_entity_store
SET increment_last_id="100001708"
WHERE entity_type_id="6" AND store_id="1"
If you have multiple stores you will have to change the store_id.
This answer is based on the info from this article.