Banning cards in Legacy is a touchy subject. Players in that format are fiercely protective of it, and especially of the particular deck or strategy they prefer to employ. Because of the power level of spells in the Eternal formats, when you Threaten the viability of a card, it has far-reaching impacts beyond the singular interactions of one plus one. Because of the high cost-of-entry in Legacy, significant shifts in the viability of decks Threaten devastating impacts on the value of individual cards and subsequently the ability of players to construct decks.
Any discussion of bannings that does not factor in the rippling impacts on potential price changes of secondary market singles is a flawed discussion. Whether Wizards of the Coast factors those fluctuations into their decision making process or not, they are an important facet in discussion the reception of a change, as well as the overall impacts to the format.
For a contemporary (at least in my prosaic timeline it's contemporary) example, consider the difference between the banning of Mystical Tutor and the banning of Survival of the Fittest. In the former example, Mystical Tutor was an integral piece of a number of combo decks, but these decks were capable of adapting beyond the loss of just the tutor. Blue/Black Reanimator, in particular was strongly weakened by the loss of Mystical, but the archetype does live on today.
While there are many subtle shifts in metagame considerations and new-card-availability decisions that impact the look of this deck, overall the archetype looks largely the same. You're still running Entomb, Reanimate, black hand disruption, and blue counter protection. Your strategy is still intact and viable. While the deck would be far, far more potent with Mystical Tutor available, it does not lose all viability with the Tutor banned.
Contrast this with Survival of the Fittest, a card that has similar impact within a deck (being a tutor for a particular card or set of cards) but which was utilized in a far different way.
Gerry was on a TEAR in 2010. It was really his year, and we all just lived in it. This deck utilized the Survival/Vengevine engine developed and first demonstrated by Caleb Durward at GP Columbus and added the Necrotic Ooze combo* to that engine to give the deck a faster win. Trying to capture this engine and combo into a deck that doesn't include the repeatable tutor of Survival makes the deck significantly less potent. In fact, no one has really been able to capitalize on this since the banning of SotF, despite attempts in a few different shells.
Ken used Buried Alive and Reanimate as a kind of pseudo-Survival that spent the mana putting these creatures directly into the graveyard, rather than cycling through them via Survival of the Fittest. Unfortunately his deck was quite a bit less stable and more prone to graveyard hate than the more stable Survival builds.
*The Ooze combo, for those not familiar, revolves around Necrotic Ooze copying both Triskelion and Phyrexian Devourer's abilities while these creatures are in the graveyard. Once the Ooze is in play and these creatures' abilities are active, you activate the Devourer ability, exiling the top card of your library and adding +1/+1 counters equal to the CMC of the exiled card. Then you utilize Triskelion's ability to Remove a +1/+1 counter to deal one damage to a target, dealing as many damage as there are counters on the Ooze. You repeat this cycle until the opponent is dead. There were complexities included in this combo due to errata on the Devourer at the time of the combo being prominent, but that errata has since been corrected and the combo is fairly straightforward under current Oracle text.
When Survival of the Fittest was banned, not only were Survivals immediately devalued from their peak in the fall/early winter of 2010, but many of the cards surrounding the powerful enchantment were also hit hard. According to the price history, Vengevine went from an all-time peak of $46 each in early 2011 (while the card was still legal in Standard) to an all-time low of $9 each in October of 2011 (just after Innistrad became legal, rotating Worldwake out). It's hard to say just how high the Elemental would have risen had Survival remained legal and Legacy players had interest in the creature, but it's easy to say the price would not have dipped as low had Standard players known the card would retain high levels of play beyond the exit from rotating formats.
For another example similar to Vengevine, consider the plight of Stoneforge Mystic – once the golden-child of Standard's best deck, even the printing of the Artificer in an intro deck couldn't prevent her from climbing to a peak of $25 each in the middle of 2011. Once the banhammer struck her anvil, she bottomed out to about $6, and rode the rail between $6-10 for some time. It wasn't until significant interest in Legacy picked up that she began to re-ascend, until she reached her all-time peak just recently; she commands about a $35 price tag today. Her Legacy playability (and let's be fair, omnipresence) is the true driver of her price, and the legality of her and her surrounding support spells have much to do with this stability.
I give you all of this background for two reasons. One, these lists are sweet and I like looking at them because I have fond memories of that time in Legacy. Two, because recently I've been thinking a lot about the overpowered cards in Legacy and what the format would look like without one or two of them.
If you're looking to spark a debate with your local Legacy community, go to a tournament and suggest that Brainstorm should be banned. I expect you would incite some very passionate dissent from the field – but let's take a look at this scenario anyway.
First, let's make a short attempt at a case for banning the card.
At the most recent major Legacy event, the Premier IQ in Syracuse coincident with the Open Series event, Brainstorm decks took seven of the Top 8 slots in the event, with four copies of the card in each deck. Of the possible 32 copies of Brainstorm, there were 28. The weekend prior, at the Premier IQ during the Invitational in Richmond, the tally was 24 Brainstorms in 6/8 decks. At the same time, the Invitational itself included 28 Brainstorms out of 32 possible, with 7/8 decks including the spell. Before that, the Premier IQ in Dallas on 3/15 included 24 Brainstorms again.
In fact, in the past month, only a single event has been logged where Brainstorm decks have not been overwhelmingly dominant. This event (the Premier IQ in Baltimore) was won by a deck designed specifically to prey on the overwhelming presence of Brainstorm decks, going so far as to play seven maindeck Red Elemental Blast effects!
A card that dominant (and this is the tip of the Iceberg – the spell has been this ubiquitous for years) would absolutely be on the short-list for bans were it not considered to be the sacred cow that it is in Legacy. Very few cards have ever approached that kind of dominance, and many that have been banned due to saturation were axed long before reaching anywhere near those numbers. On this statistic alone Brainstorm warrants a hard look.
Brainstorm also has a history of relations with the B&R list, as the spell is considered too powerful to be allowed as a four-of in Vintage. There, the high power level of the cards in the format makes looking at three spells for one mana too great an edge for allowance. How far away from a vintage deck is this, really?
Beyond even the Storm archetype, Legacy has seen recent bannings that have been laughable in the face of the existence of Brainstorm in the format. Do you really believe that Treasure Cruise is a stronger card than Brainstorm, or that the latter would require being banned if Brainstorm and its ilk were not legal in Legacy?
Paired with fetchlands, Brainstorm represents one of the game's most powerful card selection engines. Hands that are miserable have been bailed out by Brainstorm + Flooded Strand since the format's inception, causing players to lean on the spell to correct mistakes in both their game play and deck construction. It is both a draw spell and protection against disruption. It allows decks running it to reduce their land count by acting as part of the mana base. It gives combo decks additional reach, in order to find more pieces of their puzzle. It sets up Counterbalance and Delver of Secrets. It is the Swiss Army Knife of Legacy, and it comes at the low price of a single blue mana at instant speed. Ponder and Preordain, both cards that are banned in Modern and restricted in Vintage, are significantly worse than Brainstorm, and yet Brainstorm is still allowed in Legacy at full value.
If you ask players why they think Brainstorm should be allowed in Legacy, very few will come up with a better answer than "it's the only format you can play with it," or "Players will quit if you ban it." As it turns out, neither of these are compelling arguments, as you can't play with a long list of spells anywhere but Vintage anymore, and none of those bans led to a mass exodus away from Legacy. People adapt and the format would, too.
So what does a format without Brainstorm actually look like, then? Well, in all honesty it doesn't look that different from today. Where you once had Brainstorms, you'll likely have Ponder, and where Ponder already existed Preordain would fill in. Many black-based disruption strategies improve as the biggest threat to their strategy will Disappear. Combo decks would need to adapt, and their viability would be slightly reduced. Perhaps you'd see a slight decrease in the number of Fetchlands being used, as the interaction of Brainstorm/fetch would be gone – though Ponder/fetch is still pretty good and would also be sought after by blue mages. Cards that rely on the nearly-unique effect of Brainstorm to Recycle them into the library would be more difficult to utilize; Miracles would be significantly punished, as would Counterbalance. Manabases would need to be revisited, as it would be difficult to ship cards back into the library while hitting land drops, or to put extra lands back while digging for gas. The format would likely slow down slightly, though there would still be decks attempting to push the tempo both in a traditional Delver sense as well as a combo sense, though the blue-based combo decks like OmniTell and Sneak and Show would likely take the biggest hit to their viability. The format should open up a bit and allow for more diverse strategies to become viable or even powerful, which would be the ultimate goal.
Of course, we could see the opposite occur, and every deck that was Brainstorm-based simply includes the next-best cantrip. This would be similar to the impact restricting Brainstorm had in Vintage. This signifies that the ban didn't go far enough, and we could see a resulting ban of Ponder, Preordain, or both. If this were the case, then the entire structure of the Legacy format would be severely shifted, and the viability of decks like Delver would be in question. Personally, I find this concept intriguing, as I've been around the format long enough to have an idea of where it would be without Brainstorm, but starting with none of the prime cantrips causes an Upheaval like we haven't seen in a decade. The whole format would be turned on its head. While I don't mind that from a perspective of "interesting" being more important than "stable," the far-reaching impacts on format staples and the barrier of entry for new players may be too great to allow for such a change. When suddenly blue is not the de-facto best color anymore, you have a lot of players who are deeply invested into format staples left holding the potato, and that's a difficult position to put yourself in as a company.
To me, what really puts the brakes on the possibilities of this type of Paradigm Shift is the loss of identity that comes along with that big a change to the format. Right now, Modern and Legacy are very different animals – but with the removal of the major cantrips from the format, Legacy loses much of its identity and becomes more a "powered-up Modern" than a separate format as it is today. I've experienced Legacy as "Vintage lite" and it was wildly unpopular, though greatly enjoyable. Pushing the format to the other end of that spectrum would likely be the death knell for the format, as players would have little incentive to play Legacy over the much cheaper and largely similar Modern format. The good news is that should such a move be made, the price of Legacy staples would probably come down, at least temporarily, as confidence in the format would reach new lows and players actually would begin selling out of the format.
So, where does that leave us in terms of Brainstorm? I would not expect Wizards to take the card off the playable list anytime soon, they seem to have established the format as they would like it to be, and only a major oversight on their part would rock the boat far enough to warrant another look in the short-term. Despite its prevalence, Brainstorm appears to be the kind of cow at whose altar WotC doesn't mind we kneel. The effect the spell has on Legacy is largely a function of one's perspective, and while some may decide they would prefer to see what the format looks like without it, the impact of such a ban could range anywhere along the band from zero-impact to Devastation, a risk that may not be worth the taking.
In my book, something interesting needs to happen in Legacy to bring attention back to the format, as the same decks have been winning for the last few years (with a radar blip granted for the Treasure Cruise distraction). While that makes for a stable metagame and secure market value for your staples, it certainly doesn't garner interest in a format that's largely the same today as it was over 10 years ago. The bands and Musicians may have changed, but the song remains the same.