Yes, can be challenging sometimes because when you block one connection method it can try another way; particularly Skype. Nev is right, the easiest way is to stop the application from running / deny network access via the WinGate Internet Client (WGIC).
*When I want to block an instant messaging program, I use the History tab of GateKeeper, the activity windows and a packet capture utility like Ethereal to see the DNS requests; and of course google for other approaches.
So in the case of MSN Messenger:
1. When the WWW Proxy connection method is available, MSN Messenger will try to contact a resource called "gateway.dll" as seen in the history tab. To ban that resource through WinGate, you would create a policy in the WWW Proxy Service.
GateKeeper --> WWW Proxy Service --> Policies
Set the default Right to "Are Ignored" ref:
http://forums.qbik.com/viewtopic.php?p=23285#23285
GateKeeper --> WWW Proxy Service --> Policies --> Add button
Recipient tab: Everyone, user may be unknown.
Advanced tab: Add Filter, Add Criterion.
This criterion is NOT met if HTTP Resource CONTAINS gateway.dll
2. When it uses NAT it can be blocked. Navigate to:
GateKeeper --> Extended Networking --> Port Security --> Select "LAN Connections to the Internet" from the drop down list, then add a new rule for TCP 1863.
3. You may want to turn on intercepts too so the LAN Clients cannot get a direct connection to port 80 on the internet (bypassing proxy); an explanation is available from:
http://forums.qbik.com/viewtopic.php?p=23282#23282