So let us begin....
The Sametime gateway that connects a Sametime server to AIM, Yahoo or Google does currently not connect to MSN. This is not a technology shortcoming but the lack of a federation agreement between IBM and Microsoft. This post is no place to speculate who's fault that is. At the core of the problem is federation. When you use Sametime you have one identity, that makes you visible in all networks. Using a client side solution like Pidgin, Digsby, Adium, Trillian or others requires an account with each chat provider. Also it requires your firewall to be open for all these protocols for all workstations. Furthermore you won't be able to have a central logging facility which is a compliance and audit requirement in a lot of industries.
The solution approach: If Sametime traffic could run through something that handles the transition between federation and individual accounts it might do the trick (Important: this is a technical, not a legal statement!). Enter XMPP. The Sametime 7.5.1 gateway could connect to GTalk which is XMPP based. The Sametime 8.0 gateway can connect to any XMPP based server (however there is no ibm-supports-the-following-smpp-servers list). If that XMPP server connects to MSN using MSN IDs a Sametime user can talk to an MSN user. For the MSN user it will look like an MSN account (I once registered my passport account using a regular email address, so it doesn't need to be firstname.lastname@example.org or email@example.com, it can be firstname.lastname@example.org). It would work somehow like that:
I spoke to Artur Hefczyc from the Tigase project. He confirmed that Tigase has a working MSN transport and that he would work with anybody to get that working. Since Tigase is an open source project, he needs to be paid for that work.
Update: Fixed the X vs. S typo.