MSN is changing to Windows Live - part of a set of packages and changes that will make Vista more entwined with the web - this will have some affect on MSN search for a while until all is stabilized.
In "Vista" IE 7.0 will have MSN or "Live.com" which are basicly the same thing as the default search engine for users. This is a pretty big deal to Google who tried to stop it, legally, but they were unsuccessful. Current Windows platforms don't offer MSN search as the default on Internet Explorer and research has shown that most people search using the default SE of their browser so it is a big change that is coming with the release of "Vista".
I *love* MSN.co.uk! We're a UK site that have only been up for 3 months and can't get into the first 10 pages of results for our main keyword(s) on Google, but there we are on page 4 at MSN for one term, and on page 1 for another.