Raj,
The 1993 certificate format has a field (IssuerUID) that can
be used to point back to a specific instance of a CA, which would
provide the sort of back pointer that you are asking for. If we move
to the 93 format in the future this would be the preferable way to
deal with the problem you cite. However, I think it fair to note that
the time it really takes to check a signature, expecially with RSA, is
so small that it seem unlikely to be a serious problem even if a few
possible CA public keys neede to be checked. Also, because all
certificates (user and CA) carry a validity interval this info would
certainly help focus a search for the right CA certificate to use.
Our most likely source of multiple CA certificates today in PEM arises
when one CA wares multiple hats, signing certificates for users under
different policies, and we expect the fanout here to be fairly small,
e.g., maybe 2-3 when this situation arises.
Steve