Failing to join a remote room invite

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

---

### Description

Got an invite to a remote room. On clicking invite in Element web and desktop, got `{"errcode":"M_NOT_FOUND","error":"Unknown room !foobar:elokapina.fi"}` as the reply to the join.

The Element Web screenshot is rather unhelpful. The person has not left the room and the server is also not unavailable. Have done multiple attempts to ensure it's not a fluke network issue.


For the inviter in the remote room (also a remote server user), I look like joining the room. When I click accept again after the above, Synapse returns 200 to the join and the spinner just spins forever. Clearing cache and reloading does not help, the invite is still there, the room not. Told remote user to kick and re-invite, but same result.

I am in lots of rooms on with the users on the remote server. I have previously been in the room I am being invited to but having done a `/part` at some point.

Have also tried this on Element Android, the same issue except that the error is directly from the API response (ie unknown room).

If after the first unsuccessful join error on either client, I click reject invite, the remote room shows me leaving the room.

Will update Element debug logs. For Synapse debug logs, they can be found in the EMS logs.

Have tested a join from another staging Synapse in EMS and it worked.

Logging in to the Synapse tracker since I've tested this on Element desktop nightly, Element web 1.7.9 and Element Android - so it smells like a Synapse issue related to my history with the room.

### Version information

- **Homeserver**: my: federator.dev - remote: elokapina.fi

- **Version**: Both v1.21.0

- **Install method**: both Docker, official images