If you are using php then you may be able to get around this issue by recreating the session id, this is the id that is used as the unique order identifier. On your checkout failure page you will want to add this code at the bottom of the page:
<?php session_regenerate_id(); ?>
If the problem occurs because the same session id value is being used as the identifier of the order then this code should prevent this from occurring.