A "mage deck" can be interpreted in several different way: one that relies heavily on archmages, one that uses wild mages, one based on exploiting the spellstorm card, one that uses air faction, one that simply incorporates a lot of mages, mancers, etc.
Depending on what exactly you want, you might find good candidates in other threads. In particular, I am thinking of "Mages of the Storm" deck in the deck design contest thread, or possibly one of the air decks in Quintivarium's guide to AIR thread.
Here are three more decks I created in response to your request. They all work well vs. the AI but are untested in PVP. (Be particularly wary of the third as humans might far better exploit its vulnerabilities than the AI.) Honestly, this type deck is a good bit outside my preferred style, so I would imagine all three decks could be improved.
First deck: "Sea Squall" -- a deck that revolves around mages of all sorts and the spell storm card.
4 archmage -- a critical "killer" card
4 aeromancer -- good for quick attack, drawing spells, and spell storm
2 wildmage -- copy spells, good with spell storm, but costly -- you don't want many
2 chronomancer -- dispite synergy with spell storm, not a great fit for deck although cost 2 is good
4 mage tower -- durability for use with spell storm
4 energize -- great with aquamancer, but gets in the way of duplicating spell storm
4 spell storm -- critical damage inflictor
4 sea dragon -- recall spells, plus adds some muscle
4 triton aquamancer -- ridiculously over-powered plus perfect fit for deck
2 liquefy -- extremely useful and easy to shed
2 sink -- primarily to protect archmages from strength 4 creatures, but can cause you problems
4 sunken treasure -- important accelerator; don't fear wasting cards if it helps get needed cards.
Second deck: "Bombs Away" -- A combination of mages and direct damage spells that disintegrates blockers.
4 cloud dragon -- durability and magic immunity
4 archmage -- critical for killing and damage
4 aeromancers -- mainly to accelerate drawing of spells, but can cause good damage
4 arcane thief -- versatile: cheap damage, cheap one round blocker, possible power source
4 forked lightning -- cost 2 direct damage spell, fully controllable
4 magic missile -- cost 2, multi-target direct damage
2 lava elementals -- cost 2, good damage, but vulnerable
2 pyromancers -- cost 2, energy generation, good defense (never has to attack), not offensive
4 primeval flame -- blocking, ability to destroy troublesome enemies
2 meteor -- major, but last ditch enemy killer
2 fire rain -- take out low-health defenders
4 implode -- work well with you low health minions.
Third deck: "Under-Magic" -- Subversive damage bypassing opponent defenses. The deck depends upon multiple combos such as safehole or burrowing under with chronochime, overload or safe hole with aether fish, overload or damaged minions with time loop, burrowing under with overload, archmage and mage tower with spell storm, etc.
2 cloud dragon -- blocker, non-attack based damage
4 archmage -- killer of enemies, strength 3 attacks
4 aetherfish -- timer extender/remover
4 mage tower -- defense plus spell summoner, enhances spell storm
2 overload -- extra damage or strength to overpower/save
4 spell storm -- non-attack based damage
4 chronochime -- timer extender
2 time loop -- restore critical ally or reverse enemy growth
4 underdark worm -- muscle and burrowing under damage
2 deepspawn -- alternate might creature
4 burrowing under -- bypassing of enemy defense
4 safehole -- buy time for indirect damage to defeat opponent
Ok so I tweaked deck 3 this way.... I kept 1 deepspawn and 1 safe hole, in the 4 extra card spaces i put in pilfers, i played this deck yesterday and today 4 games each to see how it worked, both days i won 3/4 games and lost the other 2 due to the damn tornado card