One of the cardinal rules of X.509 is that private keys do not need to transit between entities ever. They can, certainly, and encrypting them is the correct way to do this safely (password-protected PFX files are encrypted using the passphrase to generate a symmetric key; OpenSSL exchanges encrypted keys in a similar manner but lets you explicitly choose the cipher). Exchanging the passphrase is tricky and needs to be done offline, if you don't trust the medium of transmission with the cleartext private key. Sending a cleartext private key and sending it encrypted alongside its key are exactly equivalent.
I think there is certainly a better way to do what you need to do, but it's going to be a bit of a shot in the dark because I don't understand what your service is doing with the certificates.
Generally, there are a couple goals in a setup like this:
- Mutual authentication between two endpoints
- The ability for one party to certify new users
It looks as though you want mutual authentication to be done using certificates in both directions (client certificates). You can do this without sharing a private key! The certificate your servers present only needs to be trusted by the other endpoint, not shared. So, you can exchange the fingerprint, or you can have them certify a certificate request you (automatically) generate. Or, you can generate a self-signed certificate they can trust. That's all you have to do - the certificate request, fingerprint, and certificate without key can be exchanged safely with very little risk.
As for the other side, the client can send you a CA certificate that will issue credentials. You don't need the private key to accept them, because you can validate the client's certificate against the CA certificate with which it is signed. Generally this CA certificate should not be trusted for any other purpose. This done, the client can sign all the certificates they want into authenticity, and you can either use the subject name to infer the existence of a user, or create an association between the certificate and a user in your own way.
They can safely send you the client certificates without the private key. In fact, they do this every single time they use one to authenticate.
If you do this, you create a disjoint PKI. The server authentication certificates and client authentication certificates aren't signed by the same CA; this works fine.
The clients and your servers must install the client CA and your server certificate or CA. The latter could easily be signed by a well-known CA, saving one step; installing the client CA (the CA which issues the client certificates) is standard procedure when using client certificate authentication and is probably already done in your implementation today. If you like, you can drop this down to one CA, by having a third certificate sign both those CAs (you don't need to exchange private keys to do this either; just the CSRs, containing only the public key). Then, everyone can trust that CA (again, they only need the public key to do this).
As a general simplified rule, the only time you need the private key for a certificate is if you are signing something with it ("I sent this request", "this is the key you can use to talk to me", and "I attest to the authenticity of this certificate"). Validation can always be done without the private key.
There is something funny about the way you are using X.509 here.
If a protocol depends on the client presenting your public key to authenticate, it's little better than a static (and cleartext) passphrase. In fact, it's worse, because your public key is something that is routinely disclosed. For instance, when your browser visits an HTTPS website, the server sends its public key (in the form of a certificate) to your browser. The whole point of public-key authentication is that you cryptographically sign the communications (you sign the MAC, message authentication code, which is generally a hash of the message) in a way that only you could. The client then validates that the message was signed with the private key corresponding to your certificate by checking it against the public key (in RSA they have the same modulus, but different exponents) and that the certificate is valid. Presenting the public certificate is only a small part of this.
But, then, that you are using the windows crypto API implies that perhaps you are in fact using SSL correctly, and just have the private key installed in places you wouldn't need it if you used two certificates.
All that said, you can safely exchange private keys as long as you trust the medium, which in this case I don't believe you do. You could transfer them using TLS, though that of course has its drawbacks (the key is probably of sufficient value that an attacker might actually put in the effort to recover it, breaking the conditional security assumption that the cost of recovering your information is more than its value to the attacker). If you can't trust a TLS encrypted channel for transferring it, you also can't trust the same encryption to keep it safe over the same medium in PFX (eg. AES-256 at best). Really, the safest option is to toss it on an encrypted flash drive or something and courier it. Exchanging public keys is a lot cheaper and faster and safer.
Sorry for the long rambling. TL;DR: redesign your implementation to use two CAs, one for your stuff, and one for their stuff.