[AlexTFish]

As the other repliers have explained, MtG provides various ways to circumvent that. Thus we found ways to encode millions of pieces of state in tokens, and we ensured that the game loops round computing the Turing machine execution one step at a time.

Your sentence "There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large" is actually key. You're completely right - there are many. What's unusual about our result here is that we found a way to embed a fully functional Turing machine inside not an arbitrary extension of a board game, but inside a board game exactly the way it's normally played.