This was initially reported as part of JENKINS-17965 but the fix for that issue did not fix this problem.

We have a matrix job that runs fine except that when the master does
that initial CVS update on the master prior to launching any of the matrix
builds on slaves, it gives a CVS "file was lost" error for every file in the
project.
The job is parameterized with a boolean named DELETE_WORKSPACE which is
set as the "Check parameter" for "Delete workspace before build starts" in
the Build Environment. If I set DELETE_WORKSPACE to true, the build runs
perfectly without any CVS errors which implies that my CVS authentication is
correct.
I tried running the CVS commands from the terminal window, and here's
what I see.
If I run the commands directly:
1) cvs checkout -P -d project project (this is what Jenkins does if DELETE_WORKSPACE is true)
2) cvs update -C -d -P project (this is what Jenkins does if DELETE_WORKSPACE is false)
Both CVS commands run fine.
If I let Jenkins run the first command by performing the build:
1) Run the Jenkins job with DELETE_WORKSPACE=true
2) cvs update -C -d -P project
During the cvs update, CVS gives me a bunch of warnings about locally modified files being moved to temporary files.
And if I do this:
1) Run the Jenkins job with DELETE_WORKSPACE=true
2) cvs status project
3) cvs update -C -d -P project
Then I don't get any warnings during the cvs update about locally modified files.

Michael Clarke suspects "something is going wrong with the way we manage the entries file."