Search space size is no longer a great heuristic of how difficult a game is for the latest in AI approaches. For example, an RTS game has an absolutely enormous search space as well (effectively every unit of several hundred can move in every direction for every single tick of the game clock, many units have spells and many spells are meant to stack with other spells) and Alphastar is a convincing demonstration that this is not out of the reach of current AIs. And you similarly have imperfect information where you don't know what your opponent is doing unless they are sufficiently close to your current units.

Even the meta-game/deck building aspect doesn't seem all that insurmountable as it doesn't seem fundamentally different from say a build order other than that it cannot change dynamically on the fly.

The search tree size isn't an insurmountable issue. For exple OpenAI 5 managed to play DotA (though admittedly relied heavily on perfect timing and the ability to look at every enemy on the minimap at the same time, and lost a lot when people learned to play around the only strategy it knew).I think it'd be feasible to get an AI to play a modern deck.

I think it'd be much harder for the AI to do deck building in a vacuum. You could model it as every game starting with you building your deck, but I can't see that converging stably.

MCTS is usually paired up with Deep Learning. This doesn't appear to have any problems with games with even larger branching factors. Look up AlphaZero and AlphaStar.