Steam may be detecting a changed configuration files as corrupt. That wouldn't account for the original problem, though.
Yeah that would make sense, but then the source of the original problem is a mystery (as you said).
I'd be really interested to see if QA have ever seen a bug like this before if it still occurs after a fresh install. Interaction between 2 different datasets is one thing, but if it still occurs on fresh installations then there might actually be a hard-coded issue.
It would also be nice to know if there may be remnants of my installation in the registry. Glancing through quickly I didn't see anything, but it's pretty common for games to leave some stuff behind when you uninstall them. Without a clean registry reinstallation could ultimately be pointless.