Beejive and IM+ both have paid and free versions that support MSN Messenger. Currently I'm using Trillian and I'm happy with that. It's light and fast.
I'll second that. BeejiveIM has replaced my text messaging app. It's easy on the eyes and easy to use. I refuse to pay an extra $20/mo. for something that should be included w/ a data plan.
I'm using eBuddy. I saw over at neowin.net that Microsoft will be releasing Windows Live Messenger for iPhone soon when they release Wave 4 of their Windows Live (Hotmail, Messenger, Mail, Writer, etc) products