If I am not mistaken, some of the Messenger clients can tunnel through your legitimate connections such as email, web etc.

It is almost impossible to stop them, unless you have a deep-inspection firewal that can see the real traffic inside the tunnel.

Another solution is to come out with a security policy that prohibits the use of MSN messenger, and then use Snort to detect for MSN traffic.