So many pet battles now are just people running the same meta teams over-and-over. How about a pet battle mode that chooses randomly from your level-25 blue pets and pits you against another player’s team of randomly-selected level 25 blue pets?
It would encourage thinking-on-the-fly, adaptation, and would mitigate the meta. Sure, there would be times when it’s unfair and their team is strong against yours, but it would have to be better than what we have now.
There has been a lot of discussion about PvP over the years.
Pet PvP was slapped on as a last-minute addition to battling when it was first introduced in Mists. The devs clearly had no settled idea of how it was going to develop, just … why not?
I don’t have participation numbers any more than anyone else here, but my impression is that it has gone steadily downhill, except for a bump at the introduction at Brawler, ever since.
The devs have had no interest in developing it further. Jeremy Feasel, Muffinus himself, said in an interview with Hazel that more competitive play like a rating ladder doesn’t feel right for pet battles. https://youtu.be/Ep2OUD0W2CA?t=778
Many many suggestions have been made about systems around the PvP pet battle itself - quests, lead-ins, achievements, rewards - but AFAIK all the suggestions around the core PvP pet battle itself, and The Problem Of The Meta, fall into two categories:
Buff and nerf pets every month or so, or at least every patch (though, since some patches are very long, it would probably need to be faster for those).
I think this would destroy pet battling, while not achieving the goal that I, at least, would like to see. (But since pet battling would fall off a cliff, any achievement would be theoretical anyway.)
We know our pets, and we rely on that knowledge. I don’t want my Ikky to suddenly become a tank, or my Idol to lose its defensive character. (Though I have to say again - and none of us battlers understand - WHAT were you thinking when you turned Sandstorm up to 11???)
Messing with the stats and strengths of pets would destroy the PvE game, when our regular strats and combos become unreliable every month - and the PvE game is 99%+ of battling. The tail should not try to wag the dog.
The very few PvP diehards would think it great. Everyone else would leave.
Trimming two of three OP pets every expansion is fine - Though the Sandstorm and Shattered Defenses changes were just … Whaaaaaat??? Who thoughr that made anything like sense? - but frequent mass changes and I’m out.
Your suggestion of random teams fits into this category.
The instant objection to a true random selection is that some people would prune their collection down to 5-20 of the meta pets. They’d cage their cageables, release their wild pets, and have the game select from only the cream of the crop. And you know those people are out there. 
Another common suggestion is cooldowns on pets - once you have used a pet in a PvP battle, you can’t use it in the next 10 or whatever PvP battles. We’ve done the numbers on that a couple of times, and for people with sizeable collections, it tends not to work so well.
Player-created tournaments have been tried. The usual rules agreed on by the participants have been either limited selection, like Profession-made pets only, or Wild pets from Kalimdor, or simply any pets, but for an exclusion list of 20 or so of the pets everyone is sick of seeing.
My preferred option is that each week, the game chooses a list of 50 pets at random, and during that week, you can use only those 50 pets in queued PvP. Or something along those lines. I feel it’s important that in making your team, you are choosing coverage and synergies, I have gone into the queue with 3 random pets (you can specify such a team in Rematch) and apart from being obviously weak, I find it also unsatisfying, because I had no hand in choosing it.
One big objection to all of these is the introduction of Family Brawler. With limitation on selection, it becomes near-impossible to make a Family team. There might be some niche way to work around that, like allowing people to create any Family team until they have achieved the Brawler for that Family.
I’d love to see PvP become a playable part ofthe game. I’d love to see the queue popping. Family Brawler gave me the most enjoyable couple of weeks of pet battling I had since my initial collection and learning phase in Pandaria.
But I’m not hopeful. 
Another problem with a random system IMO is that it takes the joy out of the most fun aspect of PvP - teambuilding.
Honestly, I feel that participation was stable until the last string of major changes. Instead of just nerfing Anomalus, most of the strongest pets in the game’s history have been dialed up to 11 making the meta more unbalanced than ever.
Add to that the matchmaking changes that seemed to immediately dry up everybody’s queues, and it’s no wonder that all the players who regularly made pet PvP videos and updates for pet battle addons jumped ship around the same time.
I think the easiest fix for the meta would be to undo the weather damage buffs and matchmaking and tone down Anomalus, but I’m not optimistic. At this point their only vision for pet battles seems to be incentivizing reputation grinds.
Here’s another idea. What if pets got a debuff called “Fatigued” or something like that. This debuff would specifically be from PvP (and not PvE) pet battles and would happen after X number of battles. The debuff would reset at the daily reset. When Fatigued they are too tired to battle, forcing the player to swap in other pets. It wouldn’t entirely solve the problem but would force people grinding battles all day to mix it up.
I’m sorry, Daned; I missed your post when you first made it.
The idea of a pet becoming “Fatigued” is a variant of the “cooldown” suggestion. You have introduced a wrinkle I haven’t seen before - a daily cooldown. That is interesting.
The thing to do is to set your preferred value for X and then model how it affects various use cases - the Family Brawler player, the “Must get 5K” grinder, the regular weekly 10-win plodder, and so on.
I think you may assume that at any point there are 5 most-queued pets that everyone is deadly sick of, and another 20-25 that we’d also like to avoid.
If your X is 1, then Family becomes unreasonably burdensome.
If your X is 10, then - especially given modern queue times - it would barely be noticed.
At first glance, an X somewhere between 3 and 5 … I dunno. I’d have to spreadsheet it out.
It wouldn’t much affect the regular 10-a-week case at all. Or even 10-a-day, since someone could easily still choose one from the Top-5, and 2 from the Top-20, and get through about 15 battles a day with the Undesirables. When you throw in other pets that specifically synergise with the Top-5 pets, you could doubtless cook up even more bettles per day.
Is anyone even able to catch the queue 15 times a day regularly?