If instead of allowing free deck building you offer predefined decks or only allow a small amount of customization, you can make individual cards much more powerful and crazy (= more fun) while still having the decks balanced and viable.

• Players are going to find and exploit any little imbalance or rule defect. Making balanced but different decks is a delusion.
  Optimism shouldn't be a part of your plan; did you notice how Magic: the Gathering sets contain extremely effective and narrow "hosers" for specific strategies featured in the same or previous sets? This way if some card or card group proves more powerful than expected players have the tools to fight back, correcting design errors.
  
• The freedom of deckbuilding with arbitrary cards is going to be replaced by a very limited choice between a few predefined decks. Either one of the decks is a dominant strategy, or there is a shallow rock-paper-scissor relationship. "A small amount of customization" is useless in this respect, because it simply lets players upgrade the "basic" decks to the respective optimized counterparts.
  
• Depending on how you allow deck customization, it risks being trivial (if every player has all cards and there's no room for real innovation), devolve into pay-to-win (if better cards can be simply bought), disenfranchise players (if needed cards receive a limited distribution as promos and rewards) etc.
  
  

  Another good model is where you can't pre-build a deck, but instead the players buy the stuff they need in their deck from a common card pool during the game. (See: Puzzle Strike, Dominion.)
  [/quote]
  This model makes the game fair, but not necessarily balanced enough to be fun.
  In many Dominion setups most cards are ignored as suboptimal and games are often a rush to buy the few good cards that are part of the best strategy, often with victory being decided by bad luck (drawing a useless hand is practically equivalent to skipping a turn) or good luck (drawing a good hand allows a player to buy a larger portion of the good cards sooner, or keep opponents down with attacks, or anticipate endgame moves).
  

  Other fun ways are Magic the Gathering's sealed deck and booster draft tournament modes where you build a deck out of a small pool of random cards (sealed deck) or pick cards for your deck from tiny card pools in competition with the other players (booster draft).
  [/quote]
  Don't underestimate the luck element; all deckbuilding skill in the world cannot offset the advantage of getting better cards than opponents or drafting first from a pool containing an awesome card.

Ahem, I'm not being especially optimistic. You are missing the fact that OP is talking about an online game, which can be tuned as imbalances are found. This is no different from a RTS with asymmetric factions. Do you want to try to argue that Terrans, Zerg and Protoss are horribly imbalanced in Starcraft, or have a simple rock-paper-scissors relationship?
Each Starcraft race possesses some incredibly powerful stuff which the other races do not. If you allowed players to build their own "deck" (race) with a pool of possible structures/units/abilities/tech, you'd have to nerf a lot of things to the ground and have a much blander game. The races being fixed enables the designer to create appropriate weaknesses to balance out the powerful and fun advantages.
Then there are fighting games, which always have a cast of unique characters, and tend to be quite well balanced right off the bat, even before being exposed to the community and tuned. (It is terribly expensive to fix the game when it has already been shipped to arcades, so the developers have to take balance seriously.)
I can also point to an existing card game Yomi (with physical cards, too), which has fixed decks and apparently very good balance.

• The interactions and rules are very deep and complex, so that players are unable to know all and optimize all.
  
• They are real-time games with a reflex and dexterity skill component that dwarfs the importance of asymmetric resources: games between competent players are usually lost because of errors of dexterity, distractions, bad guesses, failed gambits, etc. rather than by having weaker units or not knowing what to do.
  
  This is not the case in collectible card games, where everybody can be expected to play any deck more than decently making the content of the deck the main factor in determining victory; building a deck is where CCG strategy lies.
  Players of RTS and fighting games choose a faction or a character because they like it, because they are particularly good with it, because they think it's strong, because it's an habit, and so on; consider how playing another game with switched factions or characters or mandating "mirror matches" is a trivial and common way to neutralize any imbalance in RTS and fighting games, while swapping decks in a CCG match makes absolutely no sense.