Signature upload fails due to missing keys

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

---

Upstream bug: https://github.com/vector-im/riot-web/issues/12973

We are seeing signature uploads fail because synapse doesn't have the cross-signing keys for the user in question:

```
{
"@davetestissdjlkfghndklsfjngjlk:dbkr.me": {
"bO6OqlA3AjbjPOxW7kSfx8N5KHnDU9rjlBWiaCYQOlo": {
"status": 404,
"errcode": "M_NOT_FOUND",
"message": "404: No master key found for @davetestissdjlkfghndklsfjngjlk:dbkr.me"
}
}
}
```

One cause of this bug was https://github.com/matrix-org/synapse/issues/7252 which is now fixed but the problem still persists.

A reliable way to repro this seems to be to register fresh accounts on matrix.org and a different server, start a chat between them and then verifying the other user. The matrix.org side will fail with the above error.

No source files or tests are named. Start by reproducing the failure with fresh accounts on matrix.org and another server, then trace the signature-upload handling for the missing cross-signing key response. Done means the verification flow completes without the M_NOT_FOUND error.

Written by the indexing model from the issue text.