Might sound silly, but reinstall ICQ, and then uninstall it, all should then be OK.
Weird how it won't allow you to uninstall it in safe mode?
As I said, reinstall ICQ so it over writes the original installation and it should then allow you to remove it.
Let me know how you get on.
Kev
