Well,
The only story-based games I've beaten multiple times are, say, Ocarina of Time and Metroid Prime.
I only play games multiple times that seem to be score-based or designed for multiple play-throughs.
Like Streets of Rage, 30+ times.
Sunset Riders: 30+ times.
Ikaruga: 50+ times (and chapter 4 alone I've practiced over 90 times.)
Multiplayer I guess counts?
Warcraft 3 and Starcraft and Diablo 2 I've played for countless hours, with 4 separate Diablo 2 accounts (just this patch, I had more from a while ago) which all have characters that are 80+. Not all of them are really geared anymore though.
Unreal Tournament I've done about 5 times through the single player. I'm currently on my 6th playthrough which would be the 3rd time on Godlike. I just haven't played in a while.
Something that is sort of a "computer-based-board-game" I've played a lot of times too.
-Master of Orion (every race at least twice, Psilons and Klackons at least 5 times each).
MOO 2 (similar thing though I prefer custom races)
Civilization (Plenty of games)
Supreme Commander / Total Annihilation (plenty of skirmishes over the years)
Age of Empires (hundreds of random map generations)
Etc, etc...