What you were expecting to happen, and what actually happened:
I was expecting to face the usual explore run enemies when I started a new run after lost mini boss battle, but on battle 1 I got paired up against the same mini boss team that had defeated me previously.
How often does this happen? When did it begin happening?
Always, I guess. After noticing it today for the first time, I deliberately lost several mini boss battles (like in the screenshots above) and every time battle 1 of the new run was the mini boss team.
Exploring in a different kingdom before starting new explore in the one, where you lost the game, doesn’t change anything - battle 1 is still the same mini boss team.
Steps to make it happen again
Play explore. Get defeated in mini boss battle. Start new run.
In Explore, if you lose a match I believe you always have to replay the defense you lost to. That being said, it shouldn’t apply to Mini boss and Mythic boss since they can’t be “rematched”.