Advice on Mobile Phones with MSN/Yahoo! Messenger Installed?

I am thinking of buying a new contract phone and want some advice on which is the best contract/phone to get based on the fact I want to be able to use MSN Messenger or Yahoo! Messenger on the phone (but dont want a massive monthly bill) and want a 3G phone. Any one have any opinions on which to go with? Links to deals always welcome :)
Answers:
Try '3' http://www.three.co.uk msn messenger for their 3g network. They have improved over the passed year. They now have a gprs/wap access, which you will need to subscribe to. Although 3g browsing is free, you will find that everything will have a price. The texts cost more than other networks + cross network calls will too. But you can watch tv channels such as MTV, discovery,nickolodeon, +others.
You dont need a 3g phone to use
Hey, you'll struggle to believe this but the best deal I have found is actually on pay as you go. I'm on Orange PAYG and they do unlimited internet access (and msn for those who have it) for £1 a day, which means no nasty surprises when the bill comes! Most/all contracts offer data charged by the MB, which admittedly isn't much for using MSN but if you used it for say, 2 hours a day that would prob exceed the £1 so this is by far the most economical option if you will be using it frequently. Also, if you have a phone with full/proper internet, such as the SPV C600, then you can get full mobile net access as well for that quid. The new option is msn on the 3 network which advertises as unlimited, however check the small print and you'll find they have a 'reasonable use' policy which is pretty low! Trust me, I lived in a house with no phone line at uni last year so had to rely on using MSN on my phone, and doing it cheaply. The Orange PAYG sim card is the way to go!
Only place you can go now is on the 3 Network with MSN preinstalled. The devices like the spv series on orange that had msn on dont anymore, the license has ran out. 3 mobiles all come with msn built in. because it works in packet data sent and received the GPRS charges arent that high. works out about 3 quid a meg but its very difficult to use alot of megabytes with MSN. Alternatively you can take any 3g contract (i have a nokia 6280 and N80) and download AIM Messenger which lets you connect to AOL, yahoo and MSN on your phone
Well, if you don't like a massive bill each month, I'd advise you to go for pay-as-u-go! The deal is you only pay for the phone!
The best phone i can advise you to get that has all the top uses i.e. wap, video calling, extendable memory, mp3 etc is O2 Ice and for only £79.99 and you get a free blue tooth as well if you hurry up.
Now sim card, visit URL http://freesim.o2.co.uk and order your free sim card online. It gives you either a 1000 txt or 150 min call and 1MB of data use when you top up £10 each month!
The phone is available in all O2 shops.