Mystery solved.

It turns out that the company concerned has a strange policy in place. Their users can only access the Internet (for web browsing and email) via a Windows Terminal server machine. Which explains why all the IE output was in 8-bit color.

They only use terminal server for IE and Outlook. Presumably it is some odd attempt at centralizing security.