Personally, I'm a big fan of their short-lived 1980-1981 logo. I realize it has no place among today's clean, "Metro" look, but I love Metal and this just speaks to me. :)
Re-adopting the 1980-1981 logo would send a signal that I would love to hear. That Microsoft is rebooting Microsoft and that things are going to be new and fun again.