When viewing jobs, newer builds disappear from the build history list. Trying to go to the URL of a newer build results in a 404. The missing builds are located on disk and restarting Jenkins will make them reappear.
Sometimes, the nextBuildNumber is set to a lower number and duplicate builds are created; two date-directories are created in builds/ but only the latest build has a build_number symlink.
I wrote tool to help detect these problems on disk and even repair them (for some value of repair): https://github.com/docwhat/jenkins-job-checker
A lot of history is on
JENKINS-15156; I'll repeat some of it below.