Back in the days of Windows XP SP2, my colleagues and I were concerned about cruft on student PCs where hundreds of people would log on using roaming profiles in the course of a year. I ran a series of experiments, eventually settling on an automated stress test. Windows XP would startup, logon automatically as a domain test user and load the associated roaming profile (5-10MB), run a brief Office and Internet Explorer etc simulation opening and closing documents, save files to network home directory, then perform a clean logout/restart. I ran the script for several weeks (i.e. thousands of cycles) and observed that startup times, logon times etc were consistent, varying only with network and server loads. Free disk space went down a small amount (>3MB) after each logon and periodically Windows found more free space than the previous logon, more than could be explained for wiping out temp files etc.
A second test was devised starting with much less free space (200MB or so) on the system disk. The free space figure was guesstimated on the minimum for Windows and application temp files. This time, I also copied some data down to the system disk periodically to reduce free space. XP again displayed its mysterious ability to self repair or to run normally in an unusual situation. Startup and logon times remained consistent until free space was down to about 50MB.
I have to admit that I was very impressed that Windows XP performed so well during such abuse. The applications used for the user simulation bit were ones that behave relatively well compared to some of the junk that passes for educational or line of business software (I once promised a Geologist that I wouldn't pretend to know anything about Geology as long as Geologists stayed away from Visual Studio). We concluded that Windows XP itself and mainstream applications contributed little to cruft or performance reduction. When things were going wrong, we had to blame unidentified applications, about which we could do nothing. Annual re-imaging of student PCs, painful as it was, was an essential exercise to recover some of the performance lost over a year.
I've used cruft cleaners on home Windows installations after a mate has installed "something useful" from the internet. Cruft cleaners pick up some of the nasties more quickly than a human operated scan, even if the 3,368 "identified problems" are mostly imaginary. I've never needed one for my own PCs -- if I break them, it takes a lot more to revive them.
Incidentally, when attempting to virtualise a popular science application suite using AppV, we observed that on startup it read in tens of thousands of Registry values, everything that the suite had written. For a virtualised application with the user bit of the virtual registry on a network drive, this was unacceptable for network load and startup time. The application's publishers were unhelpful at resolving the problem. There was no need for the application to load every single Registry value -- some parts of the suite were small applications accessing only a few hundred values. We concluded that lazy programming -- just load it all -- explained it partly. But there was perhaps more. Loading the application suite Registry from a fast local disk still took a minute or two, and maybe that was the point. If you're charging £5,000 per seat for a commercial licence, the vendor needs to make it seem like a lot is happening.