Overy complex spreadsheets can be nightmares to debug and maintain. At some point if you could get the thing running to call out to Parallel Server, you would end up with adding complexity to an already complex document. Getting the complex formulas out and separating the data from the code would be a huge step forward, but also would require a decent amount of work and verification that the results are correct.
Since this sounds like it's an all Excel/MS/VB setup already, you might be able to benefit from using Microsoft HPC Server. They do have a plug-in for Excel, which allows the computations to be farmed out to a cluster -- but you would still need to do some refactoring.
I have a feeling, though, that the best long term fix is going to be to get the complex logic out of the spreadsheet where it's hard to debug and into a programming language that's easier to understand ... you can still use spreadsheets as inputs and outputs, but things like iteration, cycling through values, and producing output are much easier in a programming language. You can also version control the code and set up regression tests to ensure the model is working like it should be.
