The nextBuildNumber seem to be getting reset to a previous number. This is especially evident on high traffic jobs that get run a lot but happens even on low traffic jobs.
This causes Jenkins to build new jobs with the same build numbers and then cause the history to go crazy and to even lose builds (e.g.
Here is some output from jenkins-job-checker (a script I wrote to track these problems down):
You can see that at some point after build 10041 the nextBuildNumber got changed to 10000 and Jenkins merrily started creating duplicate builds.