I agree with Nergal here. Either that, or if iTunes is being installed differently (somehow) than it normally should be. I've also tried breaking my iTunes install via standard ccleaner install. No luck until I start adding in pathways and directories and files to be killed.
I suggest the next step is to see logs of files and registry settings that are getting changed. Clearly my first suspect of iTunes Library.itl was not the issue, and I don't feel like making any more guesses. Let's see some logs.
I found this little utility, if you're so inclined to get into looking at system changes, -- http://regshot.sourceforge.net/ -- It's basically a before and after snapshot/spy thing. It looks to see what changes have occurred to registry and filesystem. It's 100% freeware and doesn't require an install. It doesn't make changes to you computer.
From the ReadMe.txt:
Readme file of Regshot 1.9.0 (2013-02-02)
-----------------
Introduction:
-----------------
Regshot is a small, free and open-source registry compare utility that allows you to quickly
take a snapshot of your registry and then compare it with a second one - done after doing
system changes or installing a new software product. The changes report can be produced in
text or HTML format and contains a list of all modifications that have taken place between
the two snapshots. In addition, you can also specify folders (with subfolders) to be
scanned for changes as well.