Thankfully those nice folks at Wizards (who look after the DNS and hold the secondary MX for sandm.co.uk) were able to quickly move our mail to their rather excellent tidymail web mail service. We could then download mail to Outlook running on our laptops. This came in handy as we had to handle trip logistics while we were out in the US. Gmail was an option, but most folk don't know our gmail addresses.
Getting mail back into the Exchange server here wasn't a problem. We use Outlook 2003 on our laptops in "cached Exchange mode", which keeps a local copy of your entire Exchange message store. Regular readers will know that it's got us out of a tight spot after more than one server disk failure. As this rather useful Microsoft support article shows, a cached Exchange folder replicates client changes as well as server changes. So we could copy back several hundred email messages simply by running Outlook here on our home network, leaving it and Exchange to sync up.
Less than 5 minutes later and everything is in the right place.
Even the spam.
I like it when a plan comes together.
And thanks again to Wizards.