Phil Holden points out that a new version of Windows Live Messenger is available for almost all  phones, by accessing MSN Mobile, for both WAP 1.x and WAP 2.x phones.  If you've use MSN Mobile on your phone you should be good to go, if not, go to http://mobile.msn.com, and fill out the info to have a text message sent to your phone to allow you to navigate to  msn mobile, (or just browse to mobile.msn.com on your phone):

If you have a Windows Mobile phone, you'll want to use Windows Live for Mobile, or alternately, Windows Live for Nokia, but if not, the new update offers a lot of features for enabled phones:

• Rich emoticons support
• The ability to view and manage up to five active conversations
• Customers can change the display names, status etc
• Full access to your Live Contacts
• Search your contacts, hide offline contacts etc

(Update: edited to correct my noob confusion about how this works)