Outlook Encrypted Emails boo boo
Solution 1:
Encrypted mails are encrypted - if you have lost the private key and it is unrecoverable by other means, you would not have access to these messages in the foreseeable future.
To understand why this is so, you need to understand how certificates work: the public/private key pair is not generated by the CA but by the client, only the public key along with the identity information gets signed by the CA, so the CA never gets to see the private key. This is an integral part of the certificate's security - a compromised CA should not give the attacker the ability to decrypt all data encrypted in the past.
That said, if you are running an internal enterprise CA in your AD domain, chances are that your domain administrator has configured automatic key archival in the CA store. If this is the case, the CA administrator is able to recover the private key from the store.
Also, the certificate store including the keys is stored within the user's profile. So if you were using roaming profiles, this information has been copied to the server-located profile directory and likely can be recovered.