The nasty bagle worm can inhibit safemode by deleting the reg keys in XP.
This link will provide reg files for XP SP 1-3 to restore the safeboot option.
Norman 2009 seems to be a useful malware removal tool - it can run from a USB stick/CDROM and does not need to be installed. It picks up malware that even the 'industry standard' Malwarebytes does not.