"Pulled event failed history check" when backfilling

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

---

Sometimes we fail to backfill events, with warnings like the following:

```
2022-04-25 12:03:23,359 - synapse.handlers.federation_event - 684 - INFO - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - Processing pulled event
2022-04-25 12:03:23,370 - synapse.handlers.federation_event - 703 - INFO - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - De-outliering event $t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y
2022-04-25 12:03:23,373 - synapse.handlers.federation_event - 770 - INFO - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - Event $t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y is missing prev_events ['$45VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg']: calculating state for a backwards extremity
2022-04-25 12:03:23,374 - synapse.handlers.federation_event - 788 - INFO - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - Requesting state after missing prev_event $45VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg
2022-04-25 12:03:23,433 - synapse.http.matrixfederationclient - 600 - INFO - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y-$45VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg - {GET-O-718} [maunium.net] Got response headers: 404 Not Found
2022-04-25 12:03:23,434 - synapse.http.matrixfederationclient - 679 - WARNING - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y-$45VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg - {GET-O-718} [maunium.net] Request failed: GET matrix://maunium.net/_matrix/federation/v1/state_ids/%21XaqDhxuTIlvldquJaV%3Amatrix.org?event_id=%2445VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg: HttpResponseException('404: Not Found')
2022-04-25 12:03:23,434 - synapse.handlers.federation_event - 831 - WARNING - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - Error attempting to resolve state at missing prev_events
2022-04-25 12:03:23,434 - synapse.handlers.federation_event - 720 - WARNING - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - Pulled event $t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y failed history check.
```

(this is taken from an attempt to back-paginate in `#synapse-dev`.)

In this case, `$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y` is an `m.room.member` event, with a `prev_event` of `$45VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg`. Evidently, `$45V...` is a backwards extremity on `maunium.net`, because `maunium.net` is (correctly) returning `$t48H...` from the `/backfill` request, but is (also correctly) replying with a 404 to a state_ids request for `$45V...`.

We do eventually reply to the `/messages` request, but without the missing events.

Fundamentally the problem here is that the federation protocol provides no way for us to get the state before a given event (indeed, Synapse does not store that data, though it can often be inferred). Instead we have to ask for the state *after* the the event's predecessors - **which the remote server may not have**.