I believe YES
Yes, they will be deleted. In my McAfee Encryption training class, we were told to be careful and not to delete encrypted systems from ePO due to these keys. In my ePO, I tag systems that are encrypted that way I don't by mistake delete one.
The keys don't get deleted, but any machine specific policy (like the assigned users) will be.
MA will reconnect the machine and recreate it at some point - but the user list will come from the tree, not any specific assignments. ALDU might fix that for you though.
Here is a scenario:
1. We have a task running on the ePO server that automatically deletes/purges machines that have not communicated in 180 days.
2. A few months later, a user brings in a laptop that is encrypted, that they are no longer able to log in to. Will we be able to do a recovery on that machine? Or, if need be, manually decrypt it? Will we be able to access the keys somehow?
Yes you will still be able to recover/decrypt, but it won't be as simple as it would be if you left the machine in the tree. User recovery as far as I remember is not machine based so it shouldn't matter at all.
You'll have a big problem though if you delete the machine and the user breaks the encryption software - then it gets hard to find the right key to use (since the machine can't tell you anymore).
For your own sanity, you might want to think about a policy where any machine over 180days old which has not checked into EPO is considered "lost" and the only option (if found) is a user password reset, or rebuild.