I to have the very same issues! My account is an Exchange 2010 account at a major east coast university, I installed Mavericks on Thursday of release week, did an upgrade from Mountain Lion, soon discovered that mail was not arriving in my Inbox in a timely fashion. I first tried removing my account, readding, etc, no change. I was convinced it was due to the upgrade, so I made a bootable USB flash drive installer with Mavericks on it, did a clean install on a different hard drive. When the system was up and running, I added my Exchange account, after all messages were loaded I started sending test messages to myself. On my PC with Outlook up and running and my iPhone sitting next to me, I heard the notifications immediately that new mail had arrived, my Apple mail client took over 10-15 minutes to start receiving email. I tried changing settings from Automatic, 1 minute, 5 minute, none seemed to work over an extended period of time.
So, this is a real problem, not an isolated issue, the only reason I'm posting here is to add to the call for Apple to please fix this issue ASAP.
I'm going to use my Time Machine backups to revert to Mountain Lion until this issue is resolved.