Post edited.

To download a game that no longer appears in the PS Store, go to purchased category in your library.

To download said game on your PS5, go to your library and find it in the list. No search function. Make sure to sort by A-Z otherwise it’s an RNG fest. Not quite but it sure feels like it.