My first thought is the Rescue and Recovery password is not required for Safe Mode. Are you pressing F8 and specifically selecting Safe Mode?
You can download Spybot and along with that program will come a shredder that will delete that file.