This happens when we use a from token that just has a stream ordering part (which clients do the first time they start back paginating in a room after a /sync request), as the following function to convert a stream token to a topological token can lead to incorrect results:

This is a particularly big problem for rooms like Matrix HQ, where repeated calls to /messages will always trigger a backfill and then time out, even though the server has enough events to return to the client.

The problem manifests when the server receives an old event, so that it ends up with an event with a recent stream ordering but an old depth, causing the above function to return the old depth.