Payment notification but no order - SagePay

I had a customer over the weekend place an order with me for which I received a successful payment notification from SagePay, The SagePay notification also tells me the items he has ordered. However his order doesn't exists in my database. he, himself appears in my customer table but I have no reference to his order anywhere.

I'm using 1.3.9G
I can tell you the customer created his account on the 12th Nov but made the order on the 14th when he last visited. His details are showing '0' orders but I have a payment notification from sage pay. All my other order IDs for orders placed before and after his run in order with no ID numbers missing.

Can anyone help?
Tony