Kirby's Adventure. Back before the time that I could use an amazing tool called the internet. I still have all the secrets memorized, which is kinda sad.
Bomberman Hero for N64. You can't unlock Planet Gossick without getting the highest scores on all the levels, then if you're that good you shouldn't really have an issue finishing Gossick with a 5.
Zelda: Majora's Mask.
I remember because I had ABSOLUTELY EVERYTHING except one fairy. In the Great Bay Temple. (The one that's in the barrel underwater...i mean COMEON)
anyway I DID use a guide on the internet for it, but that was like..back in '03 or something. Also, I dont know if it was cheating because I KNEW the fairy was there but I didn't know how to actually ....get it.... (it was stupid easy...ugh)
I believe it was either Spyro: Year of the Dragon of Pokemon Ranger: Shadows of Almia
I know because I remember getting Spyro to 128% or whatever the highest completion percentage is, and for Pokemon I remember I made a thread on TBT asking if I'd 100%'d it, and everyone seemed to say that I had.
So it was either one of those, but I can't remember which one I completed first (part of me things is was Pokemon but idk)
Oh man, that's bringing back memories of X-X3. the shoryu and hadoken powerups particularly, and all the armor...
I want to say that I got as close to 100% on Final Fantasy Tactics on PS1 as you could get... all the characters, every rare item, etc. That'd probably be my first, but my FAVORITE 100% was Dragon Quest Heroes: Rocket Slime on DS.
I'm not sure, but it was probably something on N64 like Banjo Kazooie or Paper Mario. I never beat the sequels to either game though. Banjo Tooie and The Thousand Year Door are hard. :O