MSN don't use keyword density as much as Yahoo, MSN is more like Google back in the day in that it takes the anchor links as the most relevant factor of the page. So whats happening with your on site results are actually more an occurrence of different anchor links to the pages.
Not a single link to one of my sites and it ranks #2 out of 6,000,000 results. If anchor links determine the page rank in MSN why is my site #2 for an extremely competitive term?
I utilize the description meta with synonyms with every related term of the keywords I target and its working for me. Only thing I can assume is doing the trick! MSNDude himself announced the description meta is utilized for page rank!
I have some news pages that are in a blog-style format, with a category name following each posting. I changed some category names to include keyphrases and put them in bold. MSN didn't seem to care at all. Yahoo has been slower to update, but the one that has updated moved up to #2. It was on the second or third page before, as I recall. I didn't track it closely because I wasn't targetting Yahoo with those changes.
The one thing I've noticed that causes big reactions from MSN is anchor text on outbound links.