Whatever strategy you come up with, automate it. Please, for your own sanity, automate it. @user246 has some really good suggestions about combinatorial testing. I second that suggestion.
Since middleware, by definition sits between two systems that need to talk, your testing strategy will need to be able to ensure that your inputs to the middleware actually make it to the backing systems the way they're supposed to. You may end up writing your own testing middleware to send inputs to the system under test then read the results from the backing systems.
Testing clustering means that you'll probably be manipulating real or virtual hardware depending on your environment. I would check into Puppet or Chef for infrastructure automation to make sure that your environment is configured exactly the same time, every time you run your tests.
Only short general answers can be given here since the field of SQA is large enough to occupy the learning of many lifetimes. Good luck!