Splits and joins in PKI certificate hierarchies

I've always visualised PKI certificate hierarchies as strict trees. In this view, CA root certificates either directly authenticate end-user server and client certificates, or they authenticate multiple intermediate certificates, which may in their turn authenticate multiple further intermediate certificates, which eventually authenticate end-user certificates:

What hadn't occurred to me was that these hierarchies can also branch upward, with certificates being authenticated by more than one certificate above it:

But as it happens I've recently come across two real-live examples of this in commercial CA certificate hierarchies.

The first is in the one operated by Comodo implementing the JANET Certificate Service for UK HE sites. According to the documentation, the 'O=TERENA, CN=TERENA SSL CA' certificate chains to one ultimately authenticated by  'O=AddTrust AB, CN=AddTrust External CA Root'. But it can just as easily be verified by a commonly installed root 'O=The USERTRUST Network, CN=UTN-USERFirst-Hardware'. I've no idea why it's like this.

The second is in a hierarchy operated by Thawte. Here they are introducing a new 2048-bit root certificate, but as a precaution have also created an intermediate certificate that chains back to the old root:

This all has interesting implications for certificate verification since there are now multiple possible paths from an end user certificate to a potential root. From a little experimentation it appears that Firefox and Safari manage to find the shortest path to a configured root, but CryptoAPI (and so Internet Explorer and most of the rest of Windows) and OpenSSL take the certificate chain as provided by the server and then try verification from the end of that without ever trying to backtrack (but see note below).

This makes it impossible to take advantage of having both roots available since, taking the Thawte case, if you include the 'O=thawte, Inc., CN=thawte Primary Root CA' intermediate in the chain then your Windows/OpenSSL clients are bound to end up attempting verification against 'O=Thawte Consulting cc, CN=Thawte Premium Server CA' (and failing if they don't have it), and if you don't they will verify against the 'O=thawte, Inc., CN=thawte Primary Root CA' root (and failing if the don't have that).

The situation isn't helped by the fact that (if I'm reading it right) the relavent RFC describes verification from root to leaf even though in practice you'll always be doing it from leaf to root.

Note: subsequent further experimentation suggests that it's more complicated. Firefox does seem to be finding the shorter path in the Thawte case,  but finds the longer path in the Comodo case and fails validation if the 'O=AddTrust AB, CN=AddTrust External CA Root' is disabled. It's possible that the behaviour is influenced by other data in the various certificates.