Can’t import certificate into Exchange 2013: Private Key Missing (I know it’s there.)

I know this question has been asked before and I've gone through countless threads on here (as well as google) trying all of them. Unfortunately, I think I'm having an unrelated issue to what others have had.

I have a CRT and KEY file on our CentOS webserver. It's working fine. We want to use it on our Windows 2008 R2 Standard server for Exchange 2013.

I have verified my keyfile checks out:

# openssl rsa -text -in mydomain.key
Private-Key: (4096 bit)

I have attempted to convert it into a PFX:

# openssl pkcs12 -export -out mydomain.pfx -inkey mydomain.key -in mydomain.crt

After converting, I can even test the PFX file to make sure it does contain a private key:

# openssl pkcs12 -in exchange.pfx  -nodes
Enter Import Password:
MAC verified OK
Bag Attributes
    localKeyID: 63 04 21 C5 D8 02 0E E2 A9 A7 6E E4 CD 90 66 1E 27 95 8F 0D 
    friendlyName: My Company SSL
subject=/OU=Domain Control Validated/CN=*.mydomain.tld
issuer=/C=BE/O=GlobalSign nv-sa/CN=AlphaSSL CA - SHA256 - G2
-----BEGIN CERTIFICATE-----
(Redacted, obviously.)
-----END CERTIFICATE-----
Bag Attributes
    localKeyID: 63 04 21 C5 D8 02 0E E2 A9 A7 6E E4 CD 90 66 1E 27 95 8F 0D 
    friendlyName: My Company SSL
Key Attributes: <No Attributes>
-----BEGIN PRIVATE KEY-----
(Redacted, obviously.)
-----END PRIVATE KEY-----

Exchange allows me to import it, but then it never shows in the ECP. When I try to remove the key through the Exchange Console, this is the error I get:

[PS] C:\Windows\system32>remove-exchangecertificate

cmdlet Remove-ExchangeCertificate at command pipeline position 1
Supply values for the following parameters:
Thumbprint: 630421C5D8020EE2A9A76EE4CD90661E27958F0D

Confirm
Are you sure you want to perform this action?
Remove certificate with thumbprint 630421C5D8020EE2A9A76EE4CD90661E27958F0D from the computer's certificate store?
[Y] Yes  [A] Yes to All  [N] No  [L] No to All  [?] Help (default is "Y"): Y
A special Rpc error occurs on server TWEXCHANGE: The certificate with thumbprint
630421C5D8020EE2A9A76EE4CD90661E27958F0D was found but is not valid for use with Exchange Server (reason:
PrivateKeyMissing).
    + CategoryInfo          : NotSpecified: (:) [Remove-ExchangeCertificate], InvalidOperationException
    + FullyQualifiedErrorId : [Server=TWEXCHANGE,RequestId=75aa9cfb-6db4-4c0d-aae3-5eaa32eb0389,TimeStamp=3/25/2015 9:
   24:49 PM] [FailureCategory=Cmdlet-InvalidOperationException] DE2A4BCA,Microsoft.Exchange.Management.SystemConfigur
  ationTasks.RemoveExchangeCertificate
    + PSComputerName        : twexchange.mydomain.com

The only way to remove it is to open the MMC, add the Certificate Snap-In and connect to Computer Certificates. I can search by the SHA1 thumbprint and delete it. (If I don't delete it, when I attempt to import it again, I get an error that the thumbprint already exists.)

I've also attempted to convert my PEM key/crt file to DER and import that way:

# openssl x509 -outform der -in mydomain.pem -out mydomain.cer

I have the exact same results in Exchange 2013, it silently imports it, won't display it on the ECP and when I check it in the MMC: it's missing the private key. Any help at this point would be appreciated.