Perhaps dig in the registry to find the entries that point to Messenger, and terminate them with extrememe prejudice.

I'd say simple delete Messenger, but that irritating Windows File Protection thing would probably put it back.