Simply put, it's impossible- all SP games start to dull when you play them enough.
Simply put, incorrect. Dungeon Crawl Stone Soup achieves high replayability through heavy use of randomisation, avoidance of no-brainers and grinding. I have slightly over 16 wins in that game, and want more. Levels are randomly generated, monsters, items and traps are placed randomly. Entrances to other branches can appear on random levels (and in development version, some branches may even not appear at all in a game !). You are not guarranted to find item X or spell Y in any given game. And there's no reloading, so you either succeed or die trying.
http://crawl-ref.sourceforge.net/
If you're offended by ASCII graphics or 2D tiles, it's better to stay away.
Other heavily randomised game: Spelunky, a 2D platformer.
http://www.youtube.com/watch?v=s5IRc9uPANo
-------------
In general, I think that replayability has a lot to do with heavy randomisation of a game (level generation, random events, object placement). Additionally, it's good to make sure that there are no no-brainers. This way all choices remain viable and are not only nominally there (HOMM3 has units no one bothers to recruit like Peasants). It is wise to avoid grinding.
Repetitio est mater grindiorum
Additionaly, I think using save/continue instead of save/load helps a lot, because it makes it impossible to replay the same situation over and over.
- b0rsuk