I don't use a mac too often, but i know they have a version of windows messenger for mac osx. i'm not sure if they have built in the video messaging part. but it is the only thing i can think of.

actually, it doesn't http://messenger.msn.com/Mac/Features.aspx?client=2

I do know someone that did work from microsoft mac support, so i'll ask him if there is any beta version he knows of that could do this.