In a situation such as this (posted on Yahoo Messenger FAQ)
If you are trying to connect from behind a "smart" firewall which does not use proxy servers, Yahoo! Messenger will automatically search the firewall for an open port, and, if it finds one, use that to connect. If it's not able to find an open port, ask your System Administrator to open port 5050 to our Pager servers, cs1.yahoo.com, cs2.yahoo.com and cs3.yahoo.com.

Then I would block traffic to and from cs1,cs2,and cs3 and have done with it.