Thoughts on troubleshooting: either the server's crashing, or someone's forgetting to flush at the end of a write operation. Say, how is the server being rebooted? A script, or some built-in feature? If the former, is the script merely killing the server or is it nicely notifying the server and leaving the server to tidy up? Also, how's the autosave triggered? With a plugin, script, or CraftBukkit builtin?