Signature upload fails due to missing keys

[matrixbot]

This issue has been migrated from #7276.

---

Upstream bug: element-hq/element-web#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 matrix-org/synapse#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.