This is related to http://issues.jenkins-ci.org/browse/JENKINS-4646, but I don't seem to have comment or link permission to mention that.

If you use the clean workspace option, it only cleans the workspace on the most recently used slave. If your job runs on two slaves, it will not clear on both. The only way to fix this is to ssh to the slaves and manually clean out the workspace.