<RANT>
This is a question I get allot, especially here at Conchango since we started providing all staff with the Vodafone v1210 as our standard phones...
"Where is me Messenger?"
to which I say they (insert telco) took it out... The usual response is
"well my old one had it" - or my favorite "xyz has it on theirs!"
Well like most things in life there isn't a simple answer. Major Telco's, Vodafone being one, remove the client for a number of reasons. One of them I know for a fact is that the Windows Mobile devices are NOT being marketed as a consumer device.
Now I think to leave out the application is a mistake; two fold.
1) Virgin Lobster! Come on guys! Vodafone have been stolen a march by this device eh! This is a perfect consumer device and who needs reminding about the Orange C series... If there was every a clear indication that consumers are using it look here! This guy (yes just one guy running it!) has been doing it now for 4 years to the day. It just isn't as clear as telco's like to think it is... The clear line between consumer and business devices has long gone... Podcasting? So what if it's a business device, do business not use MSN Messenger? Nope... So not true, here at Conchango we use MSN Messenger and have been for years. Yes it's using the public system. No it's not 100% safe, can be listened into etc... But hey so can email, phones and meetings on the train! The thinking is that you will install Microsoft's Live Communications Suite in your infrastructure and then place the client on your device. Nope! So not going to happen, why would we when it's already free... I understand why banks ad other large organizations would want secure messaging, then fine, they'll have the LCS in place and will no doubt be able to demand a specific device build with LCS client inbuilt! O and the Loobster... It's got Messenger in it! 
2) XYZ Messenger - Powered by Live Messenger.... O now is marketing gone MAD! Next what? XYZ toilet paper! It's just Live in a different colour, right! Well not really, Orange is going to ensure it has interoperability with other IM platforms like MSN, Yahoo! and ICQ... But does that mean we will lose out on the COOL MSN Stuff, like voice notes, contacts integration? Lessor of two evils though I guess (in some form rather than not in at all!)
I just wish they'd stop faffing and let it stay in, well at least while they develop their own branded version...
But not is all lost, for you can have IM on your trusty Smartphone and Pocket PC no matter what them big nasty Brand hungry telco's tell you 
Here a nice man will tell you all about the new features to come in the new Live Messenger and the nicest thing about the man is he links to a BETA version you can install on your device! :)
Or you can use the Agile Messenger, A good messenger that is as agile as it suggests, works for ICQ, AIM, Yahoo! and of course MSN. It's now in BETA for version 3! But there is a cost for this (though the BETA is free)
Then of course there is the old fav, Skype... Though that's more than just IM... A WHOLE NEW BALL GAME!!!
So my advice, well, use the client that is best for you and your organization, in our case that is the Agile messenger and when/if we get an IM client or LCS we'll move...
Have you seen any good clients out there? Are you inside a telco and want to tell me if I'm wrong!
</RANT>