So I opened https://issues.jenkins-ci.org/browse/JENKINS-23098 for this, and am currently putting together the support bundle mentioned in it. But it looks like there's a very real chance that the Maven plugin/job type is just so thoroughly crap at scale that we need to get rid of it and move all jobs to freestyle projects, using Maven build steps instead.
If that turns out to be the only real option, it's going to be an ugly transition, given that we have over 600 Maven projects from many different projects, and there's no automatic way to transition those projects. I can probably come up with something that'll do a pretty decent approximation of that, but it wouldn't be perfect. We may want to consider tossing all the Maven jobs, removing the Maven plugin, and having the projects rebuild the jobs themselves. A.
