What version of EEPC are you using? Only the later versions automatically recreate the recovery information when you move them to a new server.
Encyption Agent 126.96.36.1995
I also pulled this from policy enforcement section in mfeEpe log on one of the systems:
2013-05-24 14:35:15,005 INFO MfeEpeStatusService Sent system key to Key Server
2013-05-24 14:35:15,005 INFO MfeEpeStatusService Sent recovery key to Key Server
Still getting 'No Machine Key Available' when trying to export recovery info.
Please post the orion.log from the ePO server. That may tell more.
Sorry for taking so long.
The problem ended end being user error (mine!). Since this was a test ePO server, we had installed the EE 7.0 exensions and then reverted them back. You can't do that without restoring your DB. Re-installed the the 7.0 extension and was able to get the keys back again. =-)