I'm having this problem on one of my computers too. It works fine on my W7 laptop, but not on my (you guessed it) XP SP3 desktop. Could you post the game .exe icon as a .ico file? That way I can point the shortcut to that for the icon because I'm guessing we're never going to get to the bottom of this problem...
EDIT: It's not the installer. I tried copying my Gemini Rue game exe from the W7 computer to the XP one and the icon didn't show up. I then copied that back to the W7 computer and the icon was there. For some reason my XP computer is unable to read the icon from within the program file. Given that it reads the icons from every other .exe I've come across, there has to be something different about the way the icon is embedded...