Aren't the companies also expected to do revocation checking, essentially creating a record of who identified where, with a fig leaf of "pseudonymity" (that is one database join away from being worthless)?

The revocation checking is implemented in a way where the government doesn't know who you checked and you can even cache the information (if that's good enough for you) so they won't notice at all.