Microsoft's Messenger client for OS X is crap, and unfortunately all the rest involve compromises. The only one that does video (no audio) is aMSN, and it's a sluggish, bloated mess... but it does do video.
Microsoft isn't planning on re-vamping their OS X Messenger client until 2009, I believe? Pretty pathetic.