Would it be an option for the two of you to download the standalone MSN messenger? It's free, and it's available for Macs. You can download it from
this site. (Edit: OK, stupid question. I hadn't noticed she dislikes instant messaging in general, not just the specific programs you listed.)
Theoretically, it may be possible to persuade MSN to talk to your non-IE browser. But this would require that you download the source code of an Open-Source browser like Mozilla, modify it to make the program lie to the MSN site about what type of browser it is and what operating system it is running on, then recompile. This might be a neat project if you wanted to teach yourself some hacking skills. But I imagine you don't want to, and in this case it's too difficult to be worth it.
Good luck!