On the mailing list, MPM explained the problem:

"""
The problem is that the file-level DAG is a subset of the changelog DAG
and has no way of representing two changes with (identical delta, same
parents). The only fix is to walk the entire changelog searching for all
changes that touch a given file to rebuild a complete graph. There's not
even a good way of detecting you might hit the problem without walking
the cset DAG.

Now consider that this will make all annotates on a large project take
10-100 times as long while being more accurate in only a small subset of
cases (you must have identical changes with identical parents and no
subsequent merge).
"""

So it sounds like there is no obvious/easy fix.

This may be vaguely related to issue1327.