The browser can use only the certificate that it knows of. In the case of SSL server certificates, there are three methods by which the browser will obtain the certificates needed to build a chain from a root that the browser trusts, down to the certificate to validate (in your case, the "fake"):
- The browser may have a local copy of the certificates (in a store named "intermediate CA" or something like that).
- The browser may follow the URL found in certificates themselves. A certificate may have an
Authority Information Access extension, which may point (with a URL) to a place where may be found the certificate for the issuer of the certificate which contains the extension.
- A SSL server is supposed to send its certificate as part of a fully grown chain.
The automatic download works only as long as the URL are present in the certificates, and the corresponding servers are reachable; moreover, to prevent nasty chicken-and-egg issues, the said URL shall be HTTP, not HTTPS. Not all browsers will do this download, though. It depends on the browser and also on the operating system, and their configuration. Some browsers will refuse to use anything else than the exact chain sent by the server.
So my guess is that your proxy, which acts as a SSL server, does not send a complete chain. It sends the "fake" certificate, and the "proxy intermediate CA", but not the "company intermediate CA". Thus, the browser lacks this last certificate and cannot build a complete chain.
To verify this, use OpenSSL (the command-line tool):
openssl s_client -connect www.aservername.com:443
This will print (among other information) the subject and issuer names for all certificates in the chain as sent by the server.
Alternatively, run some network monitor tool (e.g. Wireshark) to see the SSL Certificate message from the server, which contains the certificate chain from the server.
