Hi folks,
We just encountered this. Checking the Auto Increment ID of the core_email_queue table it seems the incrementer ID is less than the maximum message ID in the recipients table.
I just adjusted this to be higher than the maximum message ID and hopefully this will now be resolved.
Possibly a database optimiser has run to reset the ID but will keep an eye on it.