Accessing a Microsoft Exchange server with just my username doesn't let me read my mail, what's wrong?

This seems to be an issue when NT authentication is enabled. If your username is foo, your mailbox name is Foo.Bar and your server is FUBAR, your username for connecting to your mailbox is not foo. Instead, it would be

FUBARfooFoo.Bar