The only other answer I know of is to use a tool called RECCERTS.EXE that Microsoft Product Support has available to those who call. I can't even begin to imagine why after years of these kinds of problems people have had with EFS over and over, Microsoft still hasn't released this tool as a free download. It searches any available files it's pointed at to look for all the remnants of the keys and metadata necessary to decrypt and use the RSA private key that your previous OS install used to decrypt the EFS-encrypted files on your system. It works awfully well, but from what little documentation there is on the web (i.e. MSDN Social forum postings - latest in 2009), it appears this tool is still only available if you can find a way to convince MS Product Support to send you a copy. It appears that the cheapest official doorway here is the $99 email incident, but I wonder if they'd refund your money if you demonstrated that this fixed your problem (cf. how they used to refund - and may still do so - PSS incidents if you were able to demonstrate that there was a bug in their software for which you're calling). Not saying this is a bug, just the painful byproduct of a dubious design that doesn't warn users to take appropriate and explicit steps to avoid these recovery nightmares.
The only other possible solution is to search the web for RECCERTS.EXE and see if there are any locations where it's been made available for download. Many of such sites use legit filenames as "lures" to get you to download something that turns out to be malware, so be very careful if you take this approach. However, if your time is worth less than $99, then you just risk hosing a Windows install with nasty malware - and having to wipe & recover the system. [Just make sure there's an offline copy of the files you're trying to recover, in case the malware infects or corrupts an online, mounted copy of those files.]