For those struggling with this, two things: #1. There's an update for OSX today which supposedly deals with mail. It didn't solve the problem for me, but it's worth updating anyway. And #2. Logging into my Google Settings security page (not to be confused with Gmail settings) DID SOLVE this issue for me, though I have absolutely no idea why. Following a suggestion on this page, I logged into Gmail to check to see if I'd enabled 2-step authentication. I had NOT, which means I didn't change it... but when I clicked back over to Apple's Mail app, suddenly, all of my messages were there even though I did nothing other than log into my Google settings page to check my settings (but, again, I did not change them).
So, for me, this issue was solved (temporarily?) by simply logging into my Google settings security page. YMMV, but definitely be sure to log into your Google Settings.
I should note that I'd given up on Mail since upgrading to Mavericks once I realized messages weren't being delivered. I switched to the Airmail app (it's ok). Interestingly, Airmail seem to receive all messages, including the ones that Apple's Mail did not.