Actually, I posted fairly recently about the opposite of this happening in another thread here in this forum. I redirected about 100 URLs and all MSNBot did was request the old locations for days even though there were no links pointing at them any longer... I track the big 3 bots fairly closely on the site and know with certainty the old URLs were requested, even though they did not show up in the Bing index using the site: operator and were not linked.
Again, there were no links to the locations, internal or external and they were still requested.
* They were actually requested by all 3 search engine bots: Googlebot was the best at dumping the old locations with Slurp second and MSNBot lagging behind... Interesting to me, is what happened after the old locations were dropped, because MSNBot spidered the entire site very deeply after dropping the old locations and Slurp is still lagging behind there.
Googlebot has been the best at discovering and adjusting to the changes overall, but MSNBot is definitely second.
Some other notes on the spidering of the site I'm referring to: GBot found and spidered the XML Sitemaps first. Slurp second. MSNBot has yet to request the XML Sitemaps even though I submitted them to MSN and not either of the others. (The Sitemap Index is linked in the robots.txt according to the standard.)
There are actually a series of XML Sitemaps and GBot visits all of them frequently, Slurp has visited the main one and only requested one of the additional XML Sitemaps so far, MSNBot has not requested them at all but found most of the URLs on the site anyway.
The site has extensive HTML sitemaps for visitors and to supplement the XML Sitemaps for the bots, and these may be what MSNBot was working from to find the URLs. It was either those or standard internal links, because the site has very few inbound links and there are two new large sections to the site which have no (I mean 0) inbound links, but MSNBot has found nearly all URLs anyway.
Overall, I would have to say GBot is still the best at picking up changes, with MSNBot second and Slurp lagging way (weeks) behind... Maybe Y! decided it was to let Slurp stop at the bar to 'Slurp' something different for a change? Dunno, but IMO and from what I've seen out of the 3 MSNBot is definitely number 2 and on the way up...