A firewall is not letting Sage Pay POST information to Magento
Incorrect URLs for payment success or failure in payment request can cause this issue too.
Basically what's happening is that sagepay is contacting the website and not getting a response in the expected format. This is after the payment panel or screen has shown and the transaction is authorised.
That is enough to cancel the transaction.
To put it in context with another provider it's like cancelling a PayPal transaction if the server doesn't respond to an IPN message.
I cant express in words how much of a pain this extra step has caused me over the years.
That said sage pay pi (sagepay.js) is a step in the right direction