Andreas W: What this report is missing is information that can be used to investigate the problem. If I tried to determine the cause, I would not have any chance to do so, because what little information there is, is inconsistent. I cannot even be sure that all of the preceding comments are about either the page that's called "Build History" and contains a timeline and table, or the list of builds in the sidepanel of a single job.
Please consider filing a new bug against core. Provide as much information as you can: Jenkins logs (also create a logger for jenkins.model.PeepholePermalink at level FINE); list of plugins from /systemInfo; install Support Core plugin and attach a support bundle; describe which jobs (all? some? which?) are affected how often, does it correlate with other events in Jenkins?; what happens when you reload from disk or restart Jenkins. Maybe even add screenshots of disk contents and what the Jenkins UI shows instead, and provide a heap dump. If you want to get fancy, do some investigation yourself: Can you set up a new Jenkins instance and configure it in a way that the issue occurs there as well? You likely are a software developer or an ops guy, so provide all the information you'd want to see in an issue report!
(FWIW that goes for all readers experiencing this problem on a current version of Jenkins!)
I'm not saying none of those will get closed as duplicate of another, possibly still unresolved issue. But this should drastically increase the chance of a) someone investigating the problem b) actually finding a solution.