Microsoft does protect well your files, so you really need the key to read the files. Point.
First, try to find your files in the Recycle Bin, or try to restore your system to before you deleted the files (if still possible).
Next, try to find your deleted files, by using a file-recovery product such as PC INSPECTOR File Recovery. It can find even files not saved in the Recycle Bin.
At last, you can use a costly product called Advanced EFS Data Recovery, which will even search your hard-disk sector-by-sector for the keys. An evaluation version is available. In any case, I suggest not to write/edit files on this computer until you've exhausted all avenues of recovery.
Another less well-known product (but still costly) is EFS Key, demo available. Always use the demo, since I rather doubt that any magic wand solution is possible. The EFS encryption is rather tough!
If you manage to recover the keys, then in the future follow the advice given in these tutorials:
Back up Encrypting File System (EFS) certificate
How to back up the recovery agent Encrypting File System (EFS) private key