I moved my site to another IP address in the same C-class, and MSNbot haven't visited the site in over three weeks. It was crawling hundreds of pages daily. The MSN crawling stopped exact at the time we moved the server.
All other crawlers did continue spidering as usual after the move.
I moved a site recently and MSN was very quick to pick up the change. Did you make sure the IP you got was clean? That is to say is the Blacklist Status: Clear? Perhaps the previous owner of the address was a problem for MSN.