Is it legal to write instant message software that implements MSN Messener, Yahoo! Messener, or AIM protocols and receive money for it through ads?
Part 4 of the MSN Terms of Use says this (shortened down):
4 How You May Not Use the Service.
use any unauthorized third party software or service to access the Microsoft instant messaging network (currently known as the .NET Messenger Service);
So I would say that ads or no ads, you won't be allowed to connect to their network with anything but Live Messenger, because they don't publish an API, so the only authorized client is their own.
Stackoverflow is not a layer; Stackoverflow is not your laywer; only your lawyer may provide legal advice. Do not ask Stackoverflow for legal advice.
A lot of people do it; Pidgin, Adium, Meebo, etc. Ask your lawyer if it happens to be legal where you live. Just because MSN posts something on there site saying you can't do it doesn't mean its illegal.
They can block/kick you off the network, if you violate the ToS. Thats probably the only thing they will do, because its both easy and effective for them.
Because you've violated the ToS, there's no point in suing Microsoft for blocking your service. It depends of the country you live in, if they can claim anything from you. But as long as you're not a big company, suing you will not be profitable for them.