To block access to MSN Messenger you need to block outbound access to 1863/tcp and set a Deny URL rule towards messenger.hotmail.com over HTTP.
Yahoo Messenger is a really nasty piece of software in that it first tries port 5050, and if its not able to connect, it starts using their YMSG protocol and tunnels through every godforsaken port imaginable, even via finger, smtp and worse, through port 80, which you obviously cant deny.

Infuriating little piece of cr@p. You can try blocking the ports and setting Deny URLs msg.edit.yahoo.com/* and http.pager.yahoo.com/* but no guarantees. You can try third party blockers to block access to Yahoo or use the software restriction policy on Yahoo Messenger.