Perhaps we can try to stray from the MK comparisons a bit.
Because Bayonetta is not a Meta Knight - most complaints about her from high level players aren't that she's unbeatable. In fact it seems like a pro-ban player or two are situated between thinking she's "not good for the health of the game" and "I want to learn to beat this character because it's challenging and I like challenges".
Meta Knight was never 'officially' banned. It's a lie. Many regions opted to ban him, including the biggies (Socal, ny/ny).
Two main reasons he didn't stay banned:
1. "Blackmail" from Japan - we won't travel if you have meta knight banned.
2. Ice Climbers, a problem character with complaints since his inception similar to Bayonetta now, with similar calls to him being banned or his infinite chain grabs being banned like now who's unpopularity in the scene because of how they played and what they achieved far outweighed how strong most people agreed the character was. Suddenly ICs had dominant showings on the East Coast and most player's answers to Ice Climbers
for YEARS was a pocket meta knight; most characters were hard countered by ICs but were reasonable disadvantages against MK. It didn't take long, but MK was unbanned in regions with ICs players and not long after essentially everywhere else.
Ice Climbers never had the results MK did.
Ice Climbers never won a major tournament. Never. I think 2 ICs existing in top 8 of a large tournament was as good as it ever got.
They were an incredibly unpopular character that received a lot of flack for existing, but a community which had dealt with a MK-ban, Sirlinist arguments shoved down their throats and a general hope from most players that someone else would take them out of bracket than themselves. And if they didn't want to rely on bracket luck, they had a pocket MK trained to air stall and time them out (the only 'strategy' widely considered semi-applicable for beating them).
I'm sure you could find a lot by searching through the brawl boards for Ice Climber discussions. They would mimic a lot of thoughts and fears now.
"What if this character became efficient" "what if they never dropped their grabs?" "what if they develop their neutral game to not be explicitly about grabs?"
All the fear / theory was rejected. "MK is worse (
but worse in a totally different way) / we didn't ban him" + "we'll need to wait and see for him taking all top 8 spots at tournaments like MK never did before we would" + "Sirlinist doctrine down your throat".
Well, it took maybe 4-6 years, but the theory started showing itself. Nearly every player relied on their pocket MKs because MK had the tools to slightly negate the extremely skewed risk/reward of ICs (5 jumps + down air and tornado) which allowed a better player to beat a worse player. An extremely small remaining scene which "got over MK" because they had developed their match ups against them did not have it in them to handle ICs, many many players I know argued that they'd rather ban ICs than MK and this was a common thought process that didn't matter because the game was dead. I finally quit Brawl because of Ice Climbers, despite my belief that my character (Marth) went even at worse, I did not have it in me to continue playing a game where dash grab/back roll was so mechanically (if you didn't hit both climbers you would still get grabbed = death) stupid that despite my love for the game and the enjoyment of overcoming all the challenges, there was no answer to this and the stress was not worth it.
tl;dr
ICs were extremely unpopular characters who never could amount to the tangible dominant results of MK. Theory was there for years that this character was problematic. Communities and players far and wide were complaining about this character, arguing possible bans or limits. Regions which had prolific ICs (for example; this may be ironic: MD/VA) had a significant drop in tournament attendance/died.
@Seagull Joe could comment, there's probably more to it than just that.
It's never going to be possible to stop an ICs-like problem in a community that denotes the only bar for banishment to be Sirlinist / "top 8 results of majors being all Ice Climbers". Because that bar is never going to be achievable in modern balanced/patched games - especially if they have a "soft ban" placed upon them.
I'm not saying any fair bar has been reached right now.
But I think any 'bar' currently being suggested implies that we need to wait for active communities to give up before those who aren't experiencing these things directly will budge.
Edit: The results quote that has been highlighted here before is not really validating her being a problem, although in the last month (I believe) Bayonetta has been the most popular and successful character throughout top 16s at large tournaments (150 man or higher); this isn't indicative either.
Bayonetta is a more readily playable and popular character than Ice Climbers was and ever will be.
And they may never be as extreme as what ICs were theorized to be or shown to be. But if they're anything like what ICs forced upon players, then I vehemently disagree that waiting for the game to be dead or over saturated with results (which will be subjective and interpreted by certain people to "not be enough yet") is the right decision.