Your suspicions are correct, I believe you are experiencing an issue with the session id being reused on your subsequent orders.
The fix for this would be to either clear the session completely, or you can regenerate a new session id. Both of these should force a new session id to be created and this is usually the unique identifier for the order. There is also the Order ID session variable that is set the first time through the order. You might want to unset this value as well. You can do all this with some code like this on your checkout success or failure page:
<?php
if(!session_id())session_start();
session_regenerate_id();
unset($_SESSION['OrderID']);
?>
You should add this to the bottom of the page so it is the last code that runs. Let us know if you continue to have any problems with this.