It would have to be a game that can constantly offer NEW challenges, so a large random element has to be in play. This effectively cuts out almost all story driven games. So lets see which games can be played (almost) indefinitely, while still offering something new:
Dwarf Fortress is an obvious contender. It randomly generates its world whenever you start a new game, it is an incredibly complex game that not only offers new challenges and things to do for the player, but its AI-driven characters always seem to come up with things so funny/stupid/clever that they can get a laugh out of people who don't even play the game (like the dwarf who decides to get a pair of socks that another dwarf dropped when it got scared by a carp, only to get scarped by the carp himself, and dropping his gloves in the process, or a pair of flaming imp-skin boots, which lights dwarves on fire when they try to wear them, but as dwarves only see "new boots" when the last owner dies, they decide to take them... only to burn to death when they put them on).
Required reading [http://lparchive.org/Dwarf-Fortress-Boatmurdered/]
Luckily there are graphics mods for this game.
Civilization 2 (gold): Alright, so civilization 4 might be the better game, but for nostalgia's sake, I have to put Civ2 here
Victoria: An empire under the sun: Play as any nation during the victorian era, and try to become number 1. Deep, complex, rewarding. Any of the main Paradox games could find a spot here, but Victoria is my favourite (Victoria 2 will probably take this spot when it gets its first expansion).