I'm not sure of any easy way to reproduce. A temporary solution seems to be rebooting Jenkins.
The way that I would try to reproduce is to load Jenkins with lots of jobs and lots of builds for each job. I'm guessing that if the memory used by the job/build objects is very high in regards to the available memory (sorry - don't know how to define "high"), the problem might occur. Having the jobs limit their number of archived builds, then running many times beyond that so that archived builds are being deleted might help cause the problem; I'm guessing this because a reboot temporarily fixes our problem. And although we keep 20 to 50 builds archived on each job, we have a high enough turn over that in two weeks, all builds are replaced - and the problem seems to happen the longer we run...
Sorry for the vague and imprecise descriptions. When the problem occurs, we usually go into panic mode because Jenkins begins to fail in a variety of ways and we don't have a lot of time before we get flooded with calls from managers/engineers complaining about false build/test failure notifications, busted dashboards, etc.
Our Jenkins installation (1.496, Win2008R2) is having the same problems. A month ago, it was sporadic - once every 1000 builds or so. But we just finished adding a couple hundred more jobs and the problem got immediately worse. It's not just URLs to builds that is affected - other components also break for the same reason I suspect. The Copy Artifact plugin seems to have a similar problem. It will cause a build failure because it can't download artifacts from a specific build. This will happen repeatedly until someone uses a browser, goes to the job and specifically loads the problematic build. Once the build is display, the job can be run successfully.