Says there's icons on my Desktop that aren't there: why?

[Starkman]

So, I installed a game, deleted it, removed all remnants of it (including on the Desktop), and yet, after reinstalling it—when making a shortcut of it and putting it on the Desktop—Windows says there's already one there; do I want to continue? I mean, what's up with that?

I tried runnning a .bat program from How-To Geek (or something like that) to clean up and rebuild the icon cache, but that didn't help. Any ideas what's going on?

Thanks,

Starkman