Microprose did a very good adaptation of MtG in their time (yes, the same Microprose company), with a fairly good sandbox/adventure mode where you have to win cards by fighting against monsters and doing quests in a random map and with the objective to fight a big boss.
I has a good interface for such an old game, and in fact the interface might be similar to the MtG online
The only default is that there are only cards from the base 4th edition and some of the first extentions, so after a while you know what decks are the most effective with the cards available, and some cards are really overkill (at least, some of the most powerful like moxes and black lotus must be found in dungeons that can be hard to survive early in the game).
I just found that there was still som fan works in progress: http://www.slightlymagic.net/forum/viewforum.php?f=25
They have been able to add new cards for multiplayer and solo tournament play (but not yet for the solo sandbox it seems, or at least not in a very stable way *yet*)
In fact, I'm downloading the game now and will play again tonight. 