Clashing sessions could have something to do with it.
If you visit a site with http://www.yoursite.com
and then later visit with just http://yoursite.com
They won't share the same session, and that would cause repeated inserts with new order ids. You could also have a general issue with sessions being stored on your server. I've seen that before, but I couldn't tell without ftp access and the ability to reproduce it.