If you weren't using http proxy, it wouldn't do it for you

Creat a new network definition dns host webmessenger.msn.com and create a packet filter rule above all your access rules to reject any any webmessenger.msn.com. Between the above 2 suggestions, if the messenger is indeed coming from webmessenger.msn.com it will be blocked. If that doesn't work, create a rule for the site that you are using to access messenger and block it. Pretty trivial.