Cisco NAC and Slow Windows Startup in Domains

The Problem

A client makes extensive use of the The Cisco Network Access Control (NAC), a.k.a. Clean Access solution for their wi-fi enabled laptops. These systems are Active Directory domain members and prior to an AD upgrade, would boot and have a user logged in within 2-3 minutes.

After the domain controllers were upgrades to Windows [...]