Its certainly the type of thing that is stored in the registary.

You could try "regedit" then press CTL + F and search for windows explorer, all you have to do is press F3 and I will take you through the registary stopping at every entry that has explorer in its path.

Just look for something that doesnt look right or mentions icons I suppose!