The link you posted is correct, but I wouldn't use their fix, I would just disable the Mage_Rss module.
Mage_Rss has several observers in it that call Mage::app()->cleanCache(...) in the checkout process, which is extremely expensive if your installation is using the default filesystem cache and it's gotten large.
I found the best thing for troubleshooting Magento performance problems is to wire up Xhgui and do some profiling. Reading call stacks will help your understanding of Magento immensely also.
Oh, and I don't know if this is true for Sagepay, but I went and fixed this problem completely for PayflowPro by rewriting the method that generates transaction IDs to use the quoteID instead of generating unique IDs on every invocation. I started down the path of committing this back, but I'm on 1.4.2 still and don't have time to test in later versions and it's a pretty significant rewrite. Guess I could just put it out there for someone else to run pass Moses...