I think I've tracked down one problem whereby changelog entries can be missed.
Look at

http://deadlock.nbextras.org/hudson/job/trunk/1354/

You will see in the console

[xml] $ cvs -q -z9 update -PdC
U lexer/src/org/netbeans/lib/xml/lexer/layer.xml

This change (which BTW caused the build to break, so I care about it!) is not
mentioned in

http://deadlock.nbextras.org/hudson/job/trunk/1354/changes

Now look at the timestamp of the build:

Build #1354 (Dec 8, 2006 3:30:39 PM)

and the CVS log for this file revision:

revision 1.2
date: 2006/12/08 15:33:52; author: mfukala; state: Exp; lines: +3 -2
removed XML Language from layer since it automaticlally enabled lexer based
coloring.

What I think happened: CVSSCM.update correctly found
"xml/lexer/src/org/netbeans/lib/xml/lexer/layer.xml" and passed it (via
.checkout) to .calcChangeLog. This however calls

task.setStart(build.getPreviousBuild().getTimestamp().getTime());
task.setEnd(build.getTimestamp().getTime());

And note that the file change occurred after the build was started (3 minutes!),
while it was updating something earlier. Clearly this bug will
disproportionately affect CVS modules alphabetically near the end of large projects.

What to do? I suggest setting the end date to after update has finished. This
should permit "late" changes to be logged.

Setting the start date to the end of update for the previous build may cause
changes to be missed in this opposite direction, for an analogous reason, so I
think we cannot do this. Thus, in checkout mode, there may be duplicate
changelog entries, i.e. an entry shown in two successive builds, though this is
not as bad as missing entries. I think this would rarely occur in update mode,
since only files which were actually updated are logged; it could still occur in
case a file is patched twice in succession, I think. In the following example,
build #2 incorrectly reports patches 1.2 and 1.3 to m/f, even though 1.2 was
already in build #1:

-t0-
B0 "time: 0"
...
-t1-
B1 "time: 1"
updating a
COMMIT: m/f <- 1.2
updating m
U f
updating z
-t2-
log [t0-t2] m/f
m/f 1.2 "..."
building...
COMMIT: m/f <- 1.3
-t3-
B2 "time: 3"
updating a
updating m
U f
updating z
-t4-
log [t1-t4] m/f
m/f 1.2 "..."
m/f 1.3 "..."
building...

I suppose SVN does not suffer from this problem since you work with global
repository numbers.