I believe Yahoo messenger can be blocked with the port it uses. You can check them out with command ‘netstat -n’
If am not mistaken, MSN messenger can’t be blocked because it uses the same MSN servers for authentication and port 80. So if you wan to block it, you’ll have to block MSN sites (MSN, hotmail)
You can block these therough application signatures. You can check if ISA 2004 provides such utility.
Check websense it is a nice filtering service.