Migrated server redirects to old one

We have migrated our gitlab installation from one server to another, while changing the domain name at the same time. The old server was gitlab.domain1.com and the new one is gitlab.domain2.com.
We backed up the old server, copied the secrets and config to the new one, the restored the backup.
It works, but when opening the new server at gitlab.domain2.com, anonymous users get redirected to gitlab.domain1.com. The only page not redirected is the login page. Once logged in, users are able to use the new gitlab server without being redirected.

The config for the new server includes external_url "https://gitlab.domain2.com".

We are running Gitlab CE 13.5.3.

Duplicate of this issue: Backup with new external_url still points to old name