Since you ask, you made two statements in quick succession.
1) You don't have to be 'old school' to insist that actions have consequences.
2) The DM blew it by making the player's failure actually feel like failure.
It seems to me that if you never have to feel like you failed and if whenever you fail there is an exciting consolation prize that lets you get right back on track shortly thereafter, then you really don't believe that actions have consequences except in the most trivial way.
They - the players - blew it. The players blew it in a really big an obvious way - stopping to take a 5 minute break instead of immediately pursuing (to say nothing of completing the combat with the minion rather than trying to push past it). Those choices had a very unpleasant consequence, "The priest got away.", which I gather that the original poster is not used to experiencing because he said:
"All through that sequence of events, I though the DM was basically saying, 'back off guys, you're not going to catch this priest', putting as many obstacles in our path as possible. I felt like we needed to continue because i'm stubborn and I wanted to prove a point.
But it turns out, he actually wanted us to capture him! That was what was 'meant' to happen, which I find pretty incredible. I guess we're just looking at things from different perspectives."
The perspective of the OP implies that the OP is used to playing in a game where the things that are intended to happen by the DM, generally do happen regardless of what the players do. In this perspective, you can blow off chasing the priest until you want to, and that trial never goes cold nor does the priest ever get a headstart sufficient to get away. And that is ultimately what you seem to suggest to when you say, "The DM blew it." and "You could have at least found a clear trail"
If the player actions only had the consequence, "The priest got away today, but you'll be given another chance to get him tommorrow.", then there is really no way for the priest to get away because 'catching the priest' is the intended result. The OP's DM however seems to be suggesting that sometimes when you make an error you might not be able to recover from it at all (much less quickly) and that sometimes actions have real lasting consequences.