Have you ever tried Wine?
http://www.winehq.org/
I have never personally tried to run MSN Messenger on Linux, but I have managed to run several Windows programs as Winzip, Acrobat Reader (and Quake!!!) on RedHat, SuSe and Solaris.
Wine have been improved a lot during last year.
Anyways...if you will decide to use something else that is not MS Messenger, don't forget that Yahoo messenger does support Linux and Free BSD, it works very well.
Let me know how it goes.