As an update I have not seen any fix for this as of yet.

There is another post with the same problem I am having:

http://www.zen-cart.com/forum/showthread.php?t=46833

But this post didn't have a solution either.

Again after many more orders being placed this error is only occuring when they are being paid via PayPal. We accept 2 payment methods, PayPal and Money Order and Money Order always had the correct order # in the Gift Queue.

Since 99% of our order are via PayPal and many customers buy a Gift Certificate I am in PHPMyAdmin way too much.

Hope someone can help,
IceProducts