Finally solved this after a lot of pain...
The customer had also previously used an external drive that he was using with Memeo Backup. He had set this up to backup his WIndows Mail emails. So I tried to restore this backup onto a Vista machine with Windows Mail. However, although the folder structure was restored - absolutely no messages were restored.
I contacted Memeo about this - they say that if he'd chosen the "SmartPick" file selection then by default Windows Mail emails are NOT included?!?!? Doesn't sound very "Smart" !
This appeared to be the end of the road, but miraculously, found another backup on his laptop hard disk on the second partition - which was created a week previous to the changeover. It was created using the Static Windows Mail Backup application. Not sure who was responsible for this - the user said he didn't know anything about it.
I took a copy of this and successfully restored it to Windows Mail on a Vista machine - all the subfolders and messages were now present. I then created a new Exchange profile in Outlook on the Vista machine in order to export the messages into his mailbox on the server. But the result was I ended up with the same mess of storage folders in his mailbox.
Having done more research it certainly seems like there is a major flaw in the import/export functionality of Windows Mail that was fixed in Windows Live Mail.
So...I restored the messages into a clean copy of Windows Mail using the Static Windows Mail Backup program. Then I upgraded to Windows Live Mail allowing the install process to automatically transfer the old messages - then exported to the Exchange profile in Outlook.
And it worked!
So I guess the moral of that story is don't rely on the import/export mechanism of Windows Mail - upgrade to Windows Live Mail.