I am having troubles with OSX 10.9 Mavericks Apple Mail and MS Exchange, too. I used the Migration Assistant to pull my user account from a Time Machine Backup of a Snow Leopard system (OSX 10.6.8).
My troubles are with email RETRIEVAL DELAY. I can send email with no troubles.
I have tried REBUILD of the mailbox.
I have tried deleting the Apple Mail Account that points to the Exchange Server.
I have tried closing Mail, then moving ~/Library/Containers/com.apple.mail/Data/Library/Preferences/com.apple.mail.pli st to the Desktop, and then re-opening Mail to rebuild the com.apple.mail.plist preferences file.
I have gone into the Preferences->General and changed from Automatic to Every 1 Minute ... email retrieval is like waiting for a log jam to break free. Retrieval delay varies anywhere from a couple of minutes to a couple of hours.
I can hit the "Get new messages" button all day long and nothing happens.
My iPhone 5 (iOS 7) is pointed to the exact same MS Exchange account and it picks up emails from the server way faster than Apple Mail on Mavericks. I had no problem with Apple Mail on Snow Leopard.
I noticed that Apple Mail was updated on Nov 8, 2013, but no mention of MS Exchange enhancements or known issues list.