Is this currently possible in either Lucid or Maverick?
telepathy-butterfly which is a backend to the default Ubuntu IM client Empathy has just received support for the p2pv2 protocol, which will be the only voice/video protocol used by future version versions of the official Windows client. (see bug report and OMG! Ubuntu)
Whilst these fixes are in the source code, it will take time for a new version of
telepathy-butterfly to be released, packaged and put in Ubuntu. We are also dependant on the uptake of future versions of the official Windows client (we will be compatible with all future versions, currently in Beta testing). I imagine this will be working in a mainstream way by Ubuntu release 11.04
you can use aMSN. Its a MSN messenger clone for linux.
Not with a native client but you can through Meebo (uses Flash).
Emesene might possibly work?
emesene is a great msn chatting program and YES it has a video support till now but it makes the program crash most of the time :D .. i read lots of comments that complain about microsoft denying access to its chat servers for other apps than microsoft's messenger