If you know how to disable NAT, sure, I guess so. Unless you play online games or something that requires it?
As for that HTTP option, what it does is this: MSN is built to use specific protocols to talk to its servers. Those protocols are a really good fit to MSN's needs. But they are somewhat more demanding of the way the internet connection is set up than HTTP is. HTTP is the protocol that web browsers use to get web pages. So it works on almost any computer on the internet. So it's sort of a backup option.
See if one/either of those things help. If they do, and you see no downside, just leave well enough alone. Otherwise, it's still quite possible there's something fishy with your network setup.
One more thing to put on your list to try after those two things you're going to try (HTTP and turning NAT off), if those don't work: Go to System Preferences -> Network -> select your interface -> TCP/IP -> Configure IPV6. From there, in the pull down, select IPV6 OFF, and see if this helps. IPV6 is still very rarely used, and you don't need it, and occasionally things get screwed up because of it. Those Windows computers are 95% likely to be configured to have IPV6 off already, and that's another source of possible differences. I don't know specifically why IPV6 should cause you trouble (mine is on), but it seems to occasionally happen.