Barring Super Mario, Sonic, and other various platformers and multiplayer games, I have replayed to their completion:
Pokemon Red- Friend dropped his GB when he borrowed my cart full of Pokemon, (that included a level 99 Charizard) which erased the data. So I played again and finally caught all the Pokemon in the game.
Metal Gear Solid 3: Snake Eater- Just too good to beat once. I picked it up, and in one night replayed the entire thing (while skipping cutscenes and looking for secrets). Will probably do it again with Subsistence.
Ratchet & Clank: Going Commando- Beat this 5 times, spending 60 hours on it. Stopped on my 6th playthrough as I had basically done EVERYTHING in the game and was sick of it.
Star Wars: Knights of the Old Republic- Just so I could do light/dark side
Star Wars: Knights of the Old Republic II- see above
Fable- see above
The Legend of Zelda: Link's Awakening- Just too good to do once. Played through it twice, my first game to go through twice, and my first Zelda. Looking forward to a third go with DX.
Star Fox 64- Just addictive. Replayed it over and over.
The Legend of Zelda: Ocarina of Time- Immediately replayed upon completion and beat it again. Replayed it a second time to the water temple on someone else's save file, and I beat it a second time while playing Master Quest.
The Legend of Zelda: The Wind Waker- played it all again last year, just so I could see its complete ending. No complaints
Basically I don't usually replay many games. The former part of the above exceptions tend to be games I have restarted multiple times, but beaten once, though wouldn't mind still going back to. I have a feeling I'll play Twilight Princess more than once as well.