Ok, I have noticed that when I re-added the cards, I got emails from each bank confirming their registration.
Looking back at my emails, I can see that I received the same two emails (one from my bank for VISA and one from AMEX) announcing successful registration of the cards to Google pay.
So as far as I can tell, I must’ve done the registration on the nothing phone the first day I got it.
All in all, I have no idea why this was not working, but either way:
if you come across this, try removing and re-adding the cards
I will report back if the cards stop working again, but hopefully this was just some hiccup in the registration process that gets permanently fixed by doing this.