Signature verifying against multiple certified public keys?
From a cryptography perspective, this works as advertised; Eve and Frita can generate signature keys where a nontrivial fraction of signatures for one key will validate with the other.

That said:


It is trivial to detect this, if anyone looks.  If we suspect that Eve and Frita are colluding (which we may, if someone demonstrates a signature that validates with both public keys), then a simple computation of $\text{gcd}( N_e, N_f )$ will reveal it.  Alternatively, if someone just checks either $N_e$ or $N_f$ for small factors, that'd show that something nonkosher is going on.  While I don't believe most CA's routinely check the public keys submitted to them for small factors, there might be some that do (and it certainly would not be expensive, compared to the other operations CA's must do).
It's not clear if this is actually an attack; $S$ is a valid signature for $M$ under $Pub_e$, and Eve cannot argue that it's not.  Eve's argument of 'maybe Frita did it' doesn't address the question of 'how did Frita forge a signature of Eve's key'.
Also, as for your question of 'maybe real signatures embed a public key identifier', no, they do not.