Exodia Mage currently has a 42% overall win rate and has a play frequency less than 3%. There is nothing to fix.
The only decks it is strong against are Jade Druid and Razakus Priest. Considering your frustration, my money is on you playing one of those two decks, in which case I have no sympathy.
I have never played with Druid or Priest, I like to fool around with rogue and warlock though. Mainly miracle/tempo decks and with warlock I mess around with discard/control demons. I can see how the win-rate would be low against most decks, like any normal compilation of cards, but my point here is that I do not want to run aggro decks in order to beat it (if I can't win with tempo rogue variants/control lock).
And as for your statistics, 3% seems to be an understatement. From my most basic memory of climbing from rank 20 to 14 in the past few days, I've played against ice block mages about 30-40% of my matches. That is to say it is from rank 20 to 14 and not anything higher (so far), but to me that's a little high for one class variant.
I don't know a mage that doesn't run ice block. I mean, for 3 mana, who wouldn't run an invincibility guaruntee?
I guess after typing all of my thoughts on this thread, I am coming to realize that mage really just needs some design remaking, especially if one basic win condition is relevant for all deck variants of a class.
Dirty Rat, THE anti-combo deck card? If you run LK you can always sometimes use Death Grip as a counter, but that is much less consistent than Dirty Rat due to having to be randomly given the card and depends on the opponent having not drawn all of their minion combo pieces.
In wild you take a book out of the old Reno Lock's book, Brann + Dirty Rat & sometimes MCT.
Wouldn't playing dirty rat in a tempo rogue deck defeat the purpose of tempo? Dirty rat is fairly control oriented, etc. Not all decks run 2 card combo pieces. Dirty rat hurts me vs. other decks more than it helps with tempo mage.
However, an interesting suggestion, so maybe I will try it. Might be a great combo on turn 7 with Dirty rat+ vilespine :P but in any other circumstances, I can't really see it as being a good card.
http://www.hearthpwn.com/forums/hearthstone-general/card-discussion/186423-can-i-ask-why-ice-block-wasnt-hall-of-famed