Back from vacation. I had to write a script to search the backups for gitlab backups that had postgresqldump files with actual data.
Apparently the last "good" backup that had a good postgresqldump file was back in April (2025-04-24-090000-501/app_gitlab_v1.103.0.tar.gz.enc).
I was finally able to get it working by reapeating the restore steps:
Install the matching version of Gitlab to the backup version
Then restore by importing the backup
Not sure how exactly it got to this state, but it's finally back up and running!