How are you "uninstalling" it?

I'm not sure if this works or not, since I don't use Outlook, but using the "Set program access and defaults" seems to work to keep Windows Messenger from appearing. Trillian on my desktop is even registered in there, guess it did that when I reinstalled it for a short time for QuakeCon.

Found this suggestion via Google:
1. Open Outlook
2. Click Tools Menu
3. Click Options
4. Click Other tab
5. Uncheck Enable Instant Messaging in Outlook box
6. Click OK