I would also check that the IP number of the bot does I fact belong to Bing. Pretending to be MSNBot is pretty easy to do.
Aside: that's an interesting phenomenon JD. Did you (for a time) tell msnbot to noindex, nofollow? I wonder if.. Somewhere in the depths of bing's database, you are still on a list of sites that msnbot has effctively banned itself from crawling.