A few new thoughts:
1 - Certificates are typically delivered with the message that they protect.
The other answers covered this. There is typically no case of Bob getting Alice's certificate ahead of time. Alice (or fake Alice) will send her message, her signature and her certificate.
In a low-risk transaction, Bob will accept that the signature is properly verifiable with the public key of the certificate, that the certificate was signed by a trusted CA, and that the certificate is currently valid.
In a higher-risk transaction, Bob will also ask the CA whether or not there has been any change to Alice's status since Alice's certificate was issued. If Alice lost her key or became untrustworthy, her certificate would be revoked, and this can be verified several different ways.
Yes, it's technically possible that a malicious CA (or a malicious human with the right privileges within the entity providing the CA service) could:
- create a fake-Alice public key and certificate
- mail Bob a misleading mail that was properly signed with the fake-Alice credential, along with the fake-Alice credentials
- verify with Bob that the fake Alice credentials are trustworthy.
In fact, it would even be possible to revoke real-Alice's credentials in case Bob was wondering why Alice seemed to have 2 certificates.
2 - Why this is unlikely
As other folks said - PKI is built upon the idea that you defer your trust to the CA, and allow it to guide you trust in the credentials of the individual end entities. Alice is Alice because the CA says she is.
A CA builds it's customer base by building a solid reputation. For various capabilities of higher risk (and greater income!) a CA must pass a series of checks and verifications of both it's technical capabilities and also its internal infrastructure. Various types of 3rd parties will make sure that the protection mechanisms of the CA system and software are up to a certain standard, and that the processes of how certificates are made, how end user identities are verified and how revocation actions are performed are safe from tampering by even a malicious insider. There are audit controls and other subpoena-worthy artifacts inside the CA provider that are not able to be modified by a single rogue employee.
Such qualities are table stakes for high end certificate provisioning purposes.
So... it's possible for Crazy Eve's House of Signature Certificates to go into business with a CA infrastructure that provides NONE of these guarantees. And Crazy Eve could certainly mess with Alice's credentials as described. But the major browsers aren't going to provide Crazy Eve's Root CA as a trusted CA certificate. Major transaction systems are not going to qualify Crazy Eve's CA for issuing certs for any high end business communication... Crazy Eve will be providing certs for a cheap or free certificate offering and Bob and Alice got what they paid for.
The real tradeoff is that once Crazy Eve's CA gets a reputation for underhanded business dealings, any one who used this CA as a trusted issuer SHOULD remove them from the trusted CAs list. This will cause what little credibility the CA had to tank. If Certificate Provisioning wasn't a big part of the business, then it's not a major loss.
But any CA provider that went through the considerable time and money to be recognized and certified may find that it's not worth the risk to mess with a single communication between Bob and Alice.
3 - Any certificate is only as good as the means of verification
Getting a certificate issued by a CA can be as easy as clicking through a form and using PayPal or as hard as a serious background check, a mountain of paperwork, and signoff from legal witnesses. It all has to do with the risks of the transaction that the given entity will be performing with this credential.
Hopefully Bob mandated that if he was giving Alice $1 Million Dollars - that she didn't use a free cert from a cheap place. The money would justify the couple of hundred dollars that a high end certificate would cost.
4 - Legal stuff
If it comes to a court case, all evidence of identity provided by Alice and fake Alice will be called into question. I'd also expect that Alice's lawyers will request insight into the CA's transaction histories and audit records - in this day and age, failure to keep tamperproof audit records would be a serious lack of due diligence in an entity this important.
One might also start asking questions of any systems that certified the CA - did they know that such a breach of trust was possible? What controls do they require to prevent this sort of issue?
From there we get into the details specific to the area of jurisdiction - there's usually some relationship to the harm done and the degree of negligence or willful malice involved, but this is getting into legal territory.
If we're talking about the case where Alice has never had a transaction with the CA, the CA would be asked to provide proof of Alice's enrollment and it would come down to proving that the credentials were faked. But I'd think there would be more evidence than just Alice's signature. Did she buy this certificate? What was the method of payment? When did she procure it? How did she provide the public key, and what transactions has it performed since? From what location?
This gets into law, but there are more potential points of evidence that there may initially seem. From there we get into what's admissible in court and how must evidence be collected? But when a corporation's integrity is in question, a lot of things can be fair game - email records, log files, etc.