The problem was noticed by an Ars Technica forum regular. Lenovo appears to be hiding its crapware install in the laptop BIOS, so it gets installed even after fresh Windows installs:
A clean install with a new SSD, Win 8 DVD + wifi turned off managed to turn on a Lenovo service. If you delete the file and it reappears on reboot.
Apparently, Lenovo's using a Windows function called Microsoft Windows Platform Binary Table (WPBT), originally designed to help simplify the installation of proprietary drivers and anti-theft software.
But Lenovo's using it as a method to force the laptop to phone home to Lenovo servers so adware can be installed.
Basically, before booting Windows, the Lenovo Service Engine (LSE) built into the laptop's firmware replaces Microsoft's copy of autochk.exe with Lenovo's version. Lenovo's version then ensures that LenovoUpdate.exe and LenovoCheck.exe are present in Windows' system32 directory, with full administrative rights.
The machine then downloads Lenovo crapware and a machine that phones home to Lenovo servers.
In in April, Security researcher Roel Schouwenberg found and reported that a buffer-overflow vulnerability in the LSE (not to mention insecure network transmission) could easily be exploited by hackers.
What is amusing is that Lenovo will probably get told off by Redmond for running afoul of Microsoft's security standards regarding WBPT. It has apparently bought in tools to kill it off.