I use "Max # of builds to keep" to discard old builds.

When "Max # of builds to keep" reaches the max number set for a given job - Jenkins deletes entire folder of last label value used in this job. For example I have labels set to:
BldT with value Debug
TrgtT with value Win32
slvT with value GP

So the internal content of the job folder structure has ../BldT/Debug/TrgT/Win32/slvT/GP/..

Then when "Max # of builds to keep" is reached - directory GP is deleted. This happens to most of the jobs I have.

The only way we found to fix this is to 'Save' or 'Apply' changes in the job configuration page (without making any changes to the job). This restores the folder structure on master.

Jenkins log for when this happens is:

SEVERE: Failed to rotate log
java.io.IOException: /jenkins-server/Home/jobs/PCompiler_sshaha2/configurations/axis-BldT/Debug/axis-TrgtT/Win32/axis-slvT/GP/builds/2012-05-06_14-11-06 is in use
at hudson.model.Run.delete(Run.java:1239)
at hudson.model.AbstractBuild.delete(AbstractBuild.java:380)
at hudson.matrix.LinkedLogRotator.perform(LinkedLogRotator.java:64)
at hudson.model.Job.logRotate(Job.java:336)
at hudson.model.Run.run(Run.java:1478)
at hudson.matrix.MatrixRun.run(MatrixRun.java:146)
at hudson.model.ResourceController.execute(ResourceController.java:88)
at hudson.model.Executor.run(Executor.java:238)