I would run Trainer's Mail in 95% of the situations.
I just consider it much greater than Puzzle of Time.
I know you can play two of them at once and get two cards back from your discard pile, which is a very strong effect.
Remember however that there are other ways to get your cards back: Super Rod for Pokémon, Land Maker for Stadia, VS Seeker for Supporters, Eco Arm for Tools, Special Charge and Energy Recycler for energy cards. The only thing you can't get back in these ways is Item Cards. Items are almost all of the cards I just mentioned.
The reason I do not like Puzzle of Time too much is that it's hard to get two in your hand at once unless you run Skyla, that I never run. When you play just one, you just get to rearrange the top three cards of your deck. In comparison, Trainer's Mail allows you to take any one Trainer card (except Trainer's Mail) you reveal from the top four cards of your deck. If anything, when I used Puzzle of Time, it was mostly to check the top three cards of my deck to see if it was worth it to use Professor Sycamore or if I had to use, say, N instead.
The only decks where I would consider running Puzzle of Time are those that use lots of fast drawing cards like Acro Bike and Unown. For example, it's a great pick for Vespiquen/Vileplume. The reason I think it's worth running here is that you are going to burn lots of potentially important ressources to set up. Because you run through your deck so fast, you should be able to run into two Puzzle of Time to get those important cards back.