The EFS certificate files can be found in "%userprofile%\Application Data\Microsoft\SystemCertificates\My\Certificates". If you have the Documents and Settings directory from the old machine, you have a backup of the certificates. They are stored each in one file, named by thumbprint, with no extension.
In my quick test here, I was able to move them out, verify that the EFS certificate was gone and EFS files were not accessible, then move them back in on the same machine and had luck. Whether this will work between two machines I have not tested yet. I do not know what format these certificates are stored in.
As an aside, you can also use cert:\CurrentUser\My under Powershell, but that requires a live system, so probably is not relevant to your current question.