My vote goes to WarCraft II. I can't believe that it's still being sold to this day, albeit in a Battle.net edition. If you consider that it's more a technological update (to make it playable online) rather than an actual remake, and that the original WarCraft II was released in late 1995 while its expansion pack (integrated into the battle.net edition) came out in early 1996...
It could be argued that Myst could be considered as the oldest game on the market (originally released on the Mac in 1993), but the version currently available is a graphical remake.
Incidentally, I still have the original WarCraft battlechest (which was composed of WarCraft, WarCraft II and its expansion pack, non-compatible Battle.net, of course). And we still have the original Myst (has it been 10 years already?!?).
So, do you agree with my assessment about WarCraft II being the oldest game still on the market, or do you have another title to propose?