I contacted SagePay and they provided me with some excellent logs of what our systems were sending and receiving. The issue, in my case, was an un-writable database causing an exception to be thrown at my NotificationURL.
To answer the question, as Pekka said, Contact them.
In the mean time, check your NotificationURL isn't throwing errors.