Did you try turning Spotlight off and then on to force a reindex? Also, are you by chance running Mavericks on a separate volume and is Spotlight configured to index that volume? In other words, I know Spotlight is finding Mail, but I'm not sure if it's finding your new mail since Mavericks install or looking at the old Mail DB on your ML install.
Thanks, I just checked, that Spotlight indeed excluded my Mavericks partition from search results. The ones I saw in the results must have been on my Mountain Lion partition. Reindexing now...