If you use a mobile on T-Mobile you can get Web n Walk, contract is £7.50 a month for up to 1GB data, or prepay is a maximum charge or £1 a day for the same idea.
You can get Java based messaging apps, Sony Ericsson phones, as long as they are unbranded, and most Motorolas have IM clients built in that work via Wireless Village (
www.yamigo.com is one I use) but the refresh is slow, around once a minute.
Smartphones have IM clients available to buy, but newer models are running symbian 9.1 with either S60v3 (Nokia N series) or UIQ 3.0 (Sony Ericsson M600i/P990i) which hasn't got a great source of apps to choose form.
These apps are much better, I use Agile Messenger on my M600i and it does nearly everything MSN does on my PC, but these phone cost more as they are smartphones. I find the M600i great for text as it has a qwerty keypad and touchscreen with handwriting recognition.
WM5 phones usally have MSN built in, but you're still best on T-mobile for that for Web n Walk, and they tend to cost more from them.