Instead of generating a first key-pair in your client (which you seem to discard at after this procedure) and generating another key-pair in the server to produce the certificate, you could:
- generate a single key-pair in the client,
- turn its public key into a certification request,
- send it via HTTPS with the registration info to your issuer service,
- have the service issue the certificate and send it back,
- the client associates the certificate with the private key.
All of this can be done directly within a browser, for example, but can also be done by other clients, such as your custom SOAP-based client. It has the advantage that the private key never leaves the party meant to keep hold of it: the client doesn't even need to trust the issuer service not to have kept a copy.
Provided that you trust the HTTPS connection to be certain that the registration info was indeed sent with this particular certification request, your initial verification mechanism will be fine.
EDIT:
Following comments, it seems that you don't want your private keys to be kept for escrow on your issuing server anyway. In this case, there's no point taking the risk of transmitting the private key at all. You're not gaining anything by generating the certificate key-pair on the server; if anything, you're increasing the risk (albeit limited by the fact you're transmitting that private key over HTTPS anyway).
When you issue a certificate, the point that really matters is the binding between the requester's information and the public key that will end up in the certificate, precisely because the issuing party is signing the assertion of that binding when forming a certificate.
What you really want to make sure of is that the public key used for the certificate and the registration key shared out of bands belong to the same person. From that point of view, if they give your their public key, or if you generate it and give it back to them (with the private key) is the same. Transmitting the private key one way or another in this scheme is just unnecessary.
All you need to do is to get the public key from the request/application (in the sense that the user requests/applies for the cert), check that it came with the right registration secret, and issue the cert. You can get this public key from a CSR or just as a plain public key if you want. (The details of what the applicant may have put in the CSR are barely relevant, any good CA should discard it and only put what it has verified out of bands into the cert anyway.)
If the client has verified the HTTPS connection to your server is configured properly: strong-enough cipher suites, turning off TLS compression, and proper certificate verification, you should be guaranteed that the secret registration info and the public key came together.