after disabling it (again), open regedit and go to:
"HKEY_CURRENT_USER\Control Panel\Accessibility\StickyKeys"
Whats the value of the "Flags" key? On XP, I have 510 when "Use shortcut" is ticked, 506 when not.
Reboot.... has it changed?
Further instructions to follow based on your reply.