Thanks for your comments.

We've decided the easiest way to solve this (literally :-) is to throw more CPU at it.

However we need an awful lot more CPU than is available in a single machine, so we've created a distributed version of my solver.

This has turned into a rather interesting project, involving a couple of my collegues (and several more, anyone with a Unix box and a perl installation :-)

When it's a bit cleaner (and I've proved it works) I'll post a node all about it.