Shandalar updates – Yes, that old Duels of the Planeswalkers program is still being (unofficially) updated. People have added a ton of new cards and features such as drafting against the AI and Momir Basic. (The forum is a little hard to navigate but it has all the files that you need. Basically you just download the original version and then run the newest patch for it.)
Incantus – (PvP) Lets you play other people on the Internet with rules enforcement. It has approximately 6,000 cards and is written in Python. Forum, Screenshot
MagicEngine – (PvP) Lets you play other people on the Internet with rules enforcement. Blog, Download Site, Forum
Wagic – (PvC) Lets you play against the computer with rules enforcement. Designed to work on a Playstation Portable (PSP) but it can also run on Windows and Linux. I suggest using a gamepad for the numerous buttons. It has approximately 5,100 cards.
Blog – also has links to forum and downloads section
Deckbot - (PvC) Lets you play against the computer with rules enforcement. It has approximately 1,790 cards. The user interface is text based so you'll have imagine the beautiful card art. Deckbot is unique because you can setup the program to play itself with 2 different decks and it will tell you which deck won the most number of games.
"The idea is to let your computer to play your decks and give you the winner of one of them. With all the steps logged in a text file, you can review what can be improved in your decks." Download Site
(generically named) Deckbuilder and Rules viewer – lets you easily create decks for constructed, vintage, or of any other type. It also generates nice text spoilers. Forum, Download, It uses 7z compression which you can get here.
And here I describe a variety of other Magic programs also.