Note that the wand was under the tombstone to the right of his father's grave, not under his father's grave itself. Unless they had reason to think he had hidden something in the graveyard, it's not obvious they would have looked there.
Actually, this is evidence against Moody's theory that the graveyard was moved, since there has to be a tombstone to the right of the grave. Moody could still be correct, however, if Voldemort already recovered the wand earlier, and moved the graveyard after doing so.
Voldemort was unlikely to be able to move the graveyard after losing his body - if that happened the same way as in canon.
Update: Discussion has moved on to a new thread.
After 61 chapters of Harry Potter and the Methods of Rationality and 5 discussion threads with over 500 comments each, HPMOR discussion has graduated from the main page and moved into the Less Wrong discussion section (which seems like a more appropriate location). You can post all of your insights, speculation, and, well, discussion about Eliezer Yudkowsky's Harry Potter fanfic here.
Previous threads are available under the harry_potter tag on the main page (or: one, two, three, four, five); this and future threads will be found under the discussion section tag (since there is a separate tag system for the discussion section). See also the author page for (almost) all things HPMOR, and AdeleneDawner's Author's Notes archive for one thing that the author page is missing.
As a reminder, it's useful to indicate at the start of your comment which chapter you are commenting on. Time passes but your comment stays the same.
Spoiler Warning: this thread is full of spoilers. With few exceptions, spoilers for MOR and canon are fair game to post, without warning or rot13. More specifically: