All right guys, thanks! I finally got it working. I was doing this:
dmScreenSettings.dmDisplaySettings=DM_BITSPERPEL|DM_PELSWIDTH|DM_PELSHEIGHT;

instead of this:
dmScreenSettings.dmFields=DM_BITSPERPEL|DM_PELSWIDTH|DM_PELSHEIGHT;

Enselic: Let me correct my self here, you may be right after all, I think they still do get messed up if the resolution changes. The Gens Sega Genesis emulator just changes the bitdepth and not the resolution. Actually, thats what I needed too, just a bitdepth change, to prevent the icon screwups.