Events with lots of prev_events make backfill very slow

This issue has been migrated from [#13677](https://github.com/matrix-org/synapse/issues/13677).

---

I tried to do a backfill in Matrix HQ, and as part as the received events, I received `$k59mE1_NBJs-JP4QTza2N7VMahvLp_GlvoYLcJ821s8`. This event has 20 prev_events, almost none of which I have in my db.

For *each* of those 20 events, we then request the full state of the room (taking 24 seconds), and then have to request a lot more individual events for the state or auth_chain. Many of those events get requested each time, because their signing keys have expired, or have been invalidated, so it is impossible to find a good copy of the event (see #13676). This whole process takes at least a minute for each of the 19 missing prev_events.

The whole `/messages` request took 1787 seconds (nearly 30 minutes).