Magic (card game) at tournament level was extremely deep and strategic; Deck Construction was a real art - but unfortunately it suffered to ruthless marketing strategies that made the game to expensive, for many, to be worthwhile competing. You'd have to buy heaps of cards to stay level.
Sealed Deck and Booster Draft tournaments were where it was at, for me - relatively cheap way of playing some balanced games.
The biggest hurdle it has/had for becoming a decent game is the luck factor. In Poker, for example, you just bow out if you have a shitty deal - in Magic, you were stuck with it. No matter how good your deck was, you could draw a stuff that rendered your deck practically useless against a weaker deck.