Your best bet would likely be to block outbound requests on the yahoo IM TCP port. I'm pretty sure that a determined enough user will manage to get access, though, since those apps (yahoo,msn, etc) are pretty nasty. If they can't login via the regular TCP port, they'll try going through TCP port 80. At that point, you're not having much luck!
The only real work-around to that is to block all of the outbound requests that go to the yahoo messenger servers.