So MSN/Live/Hotmail offers alternate domain names for corporate use (sometimes referred to as vanity names) and you can IM between OCS and MSN/Live/Hotmail with the following syntax username(contoso.com)@msn.com (original post).
AOL offers this service (unsure of Yahoo!) but that same syntax won't work with AOL as their gateway doesn't support that syntax.
No word on when or if this will change in the future.
TomL LCSKid, today's post credited to Ken