The "It's regurarly observed with cvs 1.12.xx servers" warnings are your CVS server not following the CVS protocol properly (they don't set the path to CVS root in their response) and can be safely ignored if you're not having issues (I think we'd have to modify CVS Client if we wanted to prevent this message completely).
Are you able to provide the output of the rlog command for the period you were building? Feel free to obfuscate any sensitive values (repository names, paths, filenames etc) if needed. This would help greatly in recreating the issue and adding unit tests to prevent it re-occurring. Also, what comment is shown against the change if you select it on the changes page? Is it 'xxxx was originally added on branch xxxx'?
Do you have rlog output and the name of the branch you're building against? We don't apply -r since CvsLog does filtering according to version numbers so should filter out the changes we're not interested in.