This will completely remove windows messenger.

Start > Run.
Type "RunDll32 advpack.dll,LaunchINFSection %windir%\inf\msmsgs.inf,BLC.Remove" (without quotes) hit OK. Reboot.