diff --git a/changelog.d/5276.feature b/changelog.d/5276.feature
deleted file mode 100644
index 403dee086..000000000
--- a/changelog.d/5276.feature
+++ /dev/null
@@ -1,1 +0,0 @@
-Allow configuring a range for the account validity startup job.
diff --git a/changelog.d/5307.bugfix b/changelog.d/5307.bugfix
new file mode 100644
index 000000000..6b152f485
--- /dev/null
+++ b/changelog.d/5307.bugfix
@@ -0,0 +1,1 @@
+Fix bug where a notary server would sometimes forget old keys.
diff --git a/docs/sample_config.yaml b/docs/sample_config.yaml
index 493ea9ee9..edfde05a2 100644
--- a/docs/sample_config.yaml
+++ b/docs/sample_config.yaml
@@ -763,9 +763,7 @@ uploads_path: "DATADIR/uploads"
 # This means that, if a validity period is set, and Synapse is restarted (it will
 # then derive an expiration date from the current validity period), and some time
 # after that the validity period changes and Synapse is restarted, the users'
-# expiration dates won't be updated unless their account is manually renewed. This
-# date will be randomly selected within a range [now + period - d ; now + period],
-# where d is equal to 10% of the validity period.
+# expiration dates won't be updated unless their account is manually renewed.
 #
 #account_validity:
 #  enabled: True
diff --git a/synapse/config/registration.py b/synapse/config/registration.py
index aad340081..693288f93 100644
--- a/synapse/config/registration.py
+++ b/synapse/config/registration.py
@@ -39,8 +39,6 @@ class AccountValidityConfig(Config):
             else:
                 self.renew_email_subject = "Renew your %(app)s account"
 
-            self.startup_job_max_delta = self.period * 10. / 100.
-
         if self.renew_by_email_enabled and "public_baseurl" not in synapse_config:
             raise ConfigError("Can't send renewal emails without 'public_baseurl'")
 
@@ -131,9 +129,7 @@ class RegistrationConfig(Config):
         # This means that, if a validity period is set, and Synapse is restarted (it will
         # then derive an expiration date from the current validity period), and some time
         # after that the validity period changes and Synapse is restarted, the users'
-        # expiration dates won't be updated unless their account is manually renewed. This
-        # date will be randomly selected within a range [now + period - d ; now + period],
-        # where d is equal to 10%% of the validity period.
+        # expiration dates won't be updated unless their account is manually renewed.
         #
         #account_validity:
         #  enabled: True
diff --git a/synapse/crypto/keyring.py b/synapse/crypto/keyring.py
index 5756478ad..8f47469a1 100644
--- a/synapse/crypto/keyring.py
+++ b/synapse/crypto/keyring.py
@@ -394,7 +394,7 @@ class BaseV2KeyFetcher(object):
 
     @defer.inlineCallbacks
     def process_v2_response(
-        self, from_server, response_json, time_added_ms, requested_ids=[]
+        self, from_server, response_json, time_added_ms
     ):
         """Parse a 'Server Keys' structure from the result of a /key request
 
@@ -417,10 +417,6 @@ class BaseV2KeyFetcher(object):
 
             time_added_ms (int): the timestamp to record in server_keys_json
 
-            requested_ids (iterable[str]): a list of the key IDs that were requested.
-                We will store the json for these key ids as well as any that are
-                actually in the response
-
         Returns:
             Deferred[dict[str, FetchKeyResult]]: map from key_id to result object
         """
@@ -476,11 +472,6 @@ class BaseV2KeyFetcher(object):
 
         signed_key_json_bytes = encode_canonical_json(signed_key_json)
 
-        # for reasons I don't quite understand, we store this json for the key ids we
-        # requested, as well as those we got.
-        updated_key_ids = set(requested_ids)
-        updated_key_ids.update(verify_keys)
-
         yield logcontext.make_deferred_yieldable(
             defer.gatherResults(
                 [
@@ -493,7 +484,7 @@ class BaseV2KeyFetcher(object):
                         ts_expires_ms=ts_valid_until_ms,
                         key_json_bytes=signed_key_json_bytes,
                     )
-                    for key_id in updated_key_ids
+                    for key_id in verify_keys
                 ],
                 consumeErrors=True,
             ).addErrback(unwrapFirstError)
@@ -749,7 +740,6 @@ class ServerKeyFetcher(BaseV2KeyFetcher):
 
             response_keys = yield self.process_v2_response(
                 from_server=server_name,
-                requested_ids=[requested_key_id],
                 response_json=response,
                 time_added_ms=time_now_ms,
             )
diff --git a/synapse/storage/_base.py b/synapse/storage/_base.py
index 52891bb9e..3fe827cd4 100644
--- a/synapse/storage/_base.py
+++ b/synapse/storage/_base.py
@@ -16,7 +16,6 @@
 # limitations under the License.
 import itertools
 import logging
-import random
 import sys
 import threading
 import time
@@ -248,8 +247,6 @@ class SQLBaseStore(object):
                 self._check_safe_to_upsert,
             )
 
-        self.rand = random.SystemRandom()
-
         if self._account_validity.enabled:
             self._clock.call_later(
                 0.0,
@@ -311,36 +308,21 @@ class SQLBaseStore(object):
             res = self.cursor_to_dict(txn)
             if res:
                 for user in res:
-                    self.set_expiration_date_for_user_txn(
-                        txn,
-                        user["name"],
-                        use_delta=True,
-                    )
+                    self.set_expiration_date_for_user_txn(txn, user["name"])
 
         yield self.runInteraction(
             "get_users_with_no_expiration_date",
             select_users_with_no_expiration_date_txn,
         )
 
-    def set_expiration_date_for_user_txn(self, txn, user_id, use_delta=False):
+    def set_expiration_date_for_user_txn(self, txn, user_id):
         """Sets an expiration date to the account with the given user ID.
 
         Args:
              user_id (str): User ID to set an expiration date for.
-             use_delta (bool): If set to False, the expiration date for the user will be
-                now + validity period. If set to True, this expiration date will be a
-                random value in the [now + period - d ; now + period] range, d being a
-                delta equal to 10% of the validity period.
         """
         now_ms = self._clock.time_msec()
         expiration_ts = now_ms + self._account_validity.period
-
-        if use_delta:
-            expiration_ts = self.rand.randrange(
-                expiration_ts - self._account_validity.startup_job_max_delta,
-                expiration_ts,
-            )
-
         self._simple_insert_txn(
             txn,
             "account_validity",

sometimes the key notary endpoint doesn't give back the keys you asked for
Example: https://matrix.org/_matrix/key/v2/query/sw1v.org/ed25519:a_BPNW: it returns `sw1v.org/ed25519:auto`, and not the key I want.
diff --git a/tests/rest/client/v2_alpha/test_register.py b/tests/rest/client/v2_alpha/test_register.py
index 0cb6a363d..d4a1d4d50 100644
--- a/tests/rest/client/v2_alpha/test_register.py
+++ b/tests/rest/client/v2_alpha/test_register.py
@@ -436,7 +436,6 @@ class AccountValidityBackgroundJobTestCase(unittest.HomeserverTestCase):
 
     def make_homeserver(self, reactor, clock):
         self.validity_period = 10
-        self.max_delta = self.validity_period * 10. / 100.
 
         config = self.default_config()
 
@@ -454,18 +453,14 @@ class AccountValidityBackgroundJobTestCase(unittest.HomeserverTestCase):
 
     def test_background_job(self):
         """
-        Tests the same thing as test_background_job, except that it sets the
-        startup_job_max_delta parameter and checks that the expiration date is within the
-        allowed range.
+        Tests whether the account validity startup background job does the right thing,
+        which is sticking an expiration date to every account that doesn't already have
+        one.
         """
-        user_id = self.register_user("kermit_delta", "user")
-
-        self.hs.config.account_validity.startup_job_max_delta = self.max_delta
+        user_id = self.register_user("kermit", "user")
 
         now_ms = self.hs.clock.time_msec()
         self.get_success(self.store._set_expiration_date_when_missing())
 
         res = self.get_success(self.store.get_expiration_ts_for_user(user_id))
-
-        self.assertGreaterEqual(res, now_ms + self.validity_period - self.max_delta)
-        self.assertLessEqual(res, now_ms + self.validity_period)
+        self.assertEqual(res, now_ms + self.validity_period)

pip install -e .[all]
parse_log_pytest
pytest
Twisted>=17.1 mock python-subunit junitxml coverage parameterized pytest
apt-get update apt-get install -y gcc
3.6
pytest --no-header -rA --tb=line --color=no -p no:cacheprovider -W ignore::DeprecationWarning
acme==0.40.1
aiocontextvars==0.2.2
attrs @ file:///opt/conda/conda-bld/attrs_1642510447205/work
Automat==22.10.0
bcrypt==4.0.1
bleach==4.1.0
boltons==23.1.1
canonicaljson==1.5.0
certifi==2021.5.30
cffi==1.15.1
charset-normalizer==2.0.12
constantly==15.1.0
contextvars==2.4
coverage==6.2
cryptography==40.0.2
daemonize==2.5.0
defusedxml==0.7.1
elementpath==2.4.0
eliot==1.14.0
extras==1.0.0
fixtures==4.0.1
frozendict==2.4.6
hyperlink==21.0.0
idna==3.10
immutables==0.19
importlib-metadata @ file:///tmp/build/80754af9/importlib-metadata_1631916693255/work
importlib-resources==5.4.0
incremental==22.10.0
iniconfig @ file:///home/linux1/recipes/ci/iniconfig_1610983019677/work
Jinja2==3.0.3
josepy==1.13.0
jsonschema==3.2.0
junitxml==0.7
ldap3==2.9.1
lxml==5.3.1
MarkupSafe==2.0.1
-e git+https://github.com/matrix-org/synapse.git@58cce39f3a91d81f3c994d510b0a283efd468ec7#egg=matrix_synapse
matrix-synapse-ldap3==0.1.5
mock==5.2.0
more-itertools @ file:///tmp/build/80754af9/more-itertools_1637733554872/work
msgpack==1.0.5
netaddr==0.10.1
packaging @ file:///tmp/build/80754af9/packaging_1637314298585/work
parameterized==0.8.1
pbr==6.1.1
pem==21.2.0
phonenumbers==9.0.2
Pillow==8.4.0
pluggy @ file:///tmp/build/80754af9/pluggy_1615976315926/work
prometheus-client==0.3.1
psutil==7.0.0
psycopg2==2.7.7
py @ file:///opt/conda/conda-bld/py_1644396412707/work
pyasn1==0.5.1
pyasn1-modules==0.3.0
pycparser==2.21
pymacaroons==0.13.0
PyNaCl==1.5.0
pyOpenSSL==23.2.0
pyparsing @ file:///tmp/build/80754af9/pyparsing_1635766073266/work
pyRFC3339==2.0.1
pyrsistent==0.18.0
pysaml2==7.3.1
pytest==6.2.4
python-dateutil==2.9.0.post0
python-subunit==1.4.2
pytz==2025.2
PyYAML==6.0.1
requests==2.27.1
requests-toolbelt==1.0.0
sentry-sdk==2.24.1
service-identity==21.1.0
signedjson==1.1.4
simplejson==3.20.1
six==1.17.0
sortedcontainers==2.4.0
testtools==2.6.0
toml @ file:///tmp/build/80754af9/toml_1616166611790/work
treq==22.2.0
Twisted==22.4.0
txacme==0.9.3
TxSNI==0.2.0
typing_extensions @ file:///opt/conda/conda-bld/typing_extensions_1647553014482/work
unpaddedbase64==2.1.0
urllib3==1.26.20
webencodings==0.5.1
xmlschema==1.9.2
zipp @ file:///tmp/build/80754af9/zipp_1633618647012/work
zope.interface==5.5.2

name: synapse
channels:
  - defaults
  - https://repo.anaconda.com/pkgs/main
  - https://repo.anaconda.com/pkgs/r
  - conda-forge
dependencies:
  - _libgcc_mutex=0.1=main
  - _openmp_mutex=5.1=1_gnu
  - attrs=21.4.0=pyhd3eb1b0_0
  - ca-certificates=2025.2.25=h06a4308_0
  - certifi=2021.5.30=py36h06a4308_0
  - importlib-metadata=4.8.1=py36h06a4308_0
  - importlib_metadata=4.8.1=hd3eb1b0_0
  - iniconfig=1.1.1=pyhd3eb1b0_0
  - ld_impl_linux-64=2.40=h12ee557_0
  - libffi=3.3=he6710b0_2
  - libgcc-ng=11.2.0=h1234567_1
  - libgomp=11.2.0=h1234567_1
  - libstdcxx-ng=11.2.0=h1234567_1
  - more-itertools=8.12.0=pyhd3eb1b0_0
  - ncurses=6.4=h6a678d5_0
  - openssl=1.1.1w=h7f8727e_0
  - packaging=21.3=pyhd3eb1b0_0
  - pip=21.2.2=py36h06a4308_0
  - pluggy=0.13.1=py36h06a4308_0
  - py=1.11.0=pyhd3eb1b0_0
  - pyparsing=3.0.4=pyhd3eb1b0_0
  - pytest=6.2.4=py36h06a4308_2
  - python=3.6.13=h12debd9_1
  - readline=8.2=h5eee18b_0
  - setuptools=58.0.4=py36h06a4308_0
  - sqlite=3.45.3=h5eee18b_0
  - tk=8.6.14=h39e8969_0
  - toml=0.10.2=pyhd3eb1b0_0
  - typing_extensions=4.1.1=pyh06a4308_0
  - wheel=0.37.1=pyhd3eb1b0_0
  - xz=5.6.4=h5eee18b_1
  - zipp=3.6.0=pyhd3eb1b0_0
  - zlib=1.2.13=h5eee18b_1
  - pip:
      - acme==0.40.1
      - aiocontextvars==0.2.2
      - automat==22.10.0
      - bcrypt==4.0.1
      - bleach==4.1.0
      - boltons==23.1.1
      - canonicaljson==1.5.0
      - cffi==1.15.1
      - charset-normalizer==2.0.12
      - constantly==15.1.0
      - contextvars==2.4
      - coverage==6.2
      - cryptography==40.0.2
      - daemonize==2.5.0
      - defusedxml==0.7.1
      - elementpath==2.4.0
      - eliot==1.14.0
      - extras==1.0.0
      - fixtures==4.0.1
      - frozendict==2.4.6
      - hyperlink==21.0.0
      - idna==3.10
      - immutables==0.19
      - importlib-resources==5.4.0
      - incremental==22.10.0
      - jinja2==3.0.3
      - josepy==1.13.0
      - jsonschema==3.2.0
      - junitxml==0.7
      - ldap3==2.9.1
      - lxml==5.3.1
      - markupsafe==2.0.1
      - matrix-synapse-ldap3==0.1.5
      - mock==5.2.0
      - msgpack==1.0.5
      - netaddr==0.10.1
      - parameterized==0.8.1
      - pbr==6.1.1
      - pem==21.2.0
      - phonenumbers==9.0.2
      - pillow==8.4.0
      - prometheus-client==0.3.1
      - psutil==7.0.0
      - psycopg2==2.7.7
      - pyasn1==0.5.1
      - pyasn1-modules==0.3.0
      - pycparser==2.21
      - pymacaroons==0.13.0
      - pynacl==1.5.0
      - pyopenssl==23.2.0
      - pyrfc3339==2.0.1
      - pyrsistent==0.18.0
      - pysaml2==7.3.1
      - python-dateutil==2.9.0.post0
      - python-subunit==1.4.2
      - pytz==2025.2
      - pyyaml==6.0.1
      - requests==2.27.1
      - requests-toolbelt==1.0.0
      - sentry-sdk==2.24.1
      - service-identity==21.1.0
      - signedjson==1.1.4
      - simplejson==3.20.1
      - six==1.17.0
      - sortedcontainers==2.4.0
      - testtools==2.6.0
      - treq==22.2.0
      - twisted==22.4.0
      - txacme==0.9.3
      - txsni==0.2.0
      - unpaddedbase64==2.1.0
      - urllib3==1.26.20
      - webencodings==0.5.1
      - xmlschema==1.9.2
      - zope-interface==5.5.2
prefix: /opt/conda/envs/synapse

tests/rest/client/v2_alpha/test_register.py::AccountValidityBackgroundJobTestCase::test_background_job
tests/rest/client/v2_alpha/test_register.py::RegisterRestServletTestCase::test_POST_appservice_registration_invalid tests/rest/client/v2_alpha/test_register.py::RegisterRestServletTestCase::test_POST_appservice_registration_valid tests/rest/client/v2_alpha/test_register.py::RegisterRestServletTestCase::test_POST_bad_password tests/rest/client/v2_alpha/test_register.py::RegisterRestServletTestCase::test_POST_bad_username tests/rest/client/v2_alpha/test_register.py::RegisterRestServletTestCase::test_POST_disabled_guest_registration tests/rest/client/v2_alpha/test_register.py::RegisterRestServletTestCase::test_POST_disabled_registration tests/rest/client/v2_alpha/test_register.py::RegisterRestServletTestCase::test_POST_guest_registration tests/rest/client/v2_alpha/test_register.py::RegisterRestServletTestCase::test_POST_ratelimiting tests/rest/client/v2_alpha/test_register.py::RegisterRestServletTestCase::test_POST_ratelimiting_guest tests/rest/client/v2_alpha/test_register.py::RegisterRestServletTestCase::test_POST_user_valid tests/rest/client/v2_alpha/test_register.py::AccountValidityTestCase::test_manual_expire tests/rest/client/v2_alpha/test_register.py::AccountValidityTestCase::test_manual_renewal tests/rest/client/v2_alpha/test_register.py::AccountValidityTestCase::test_validity_period tests/rest/client/v2_alpha/test_register.py::AccountValidityRenewalByEmailTestCase::test_manual_email_send tests/rest/client/v2_alpha/test_register.py::AccountValidityRenewalByEmailTestCase::test_renewal_email
synapse/storage/_base.py synapse/crypto/keyring.py changelog.d/5307.bugfix docs/sample_config.yaml synapse/config/registration.py changelog.d/5276.feature
synapse/storage/_base.py synapse/crypto/keyring.py changelog.d/5307.bugfix docs/sample_config.yaml synapse/config/registration.py changelog.d/5276.feature