As far as I know, I had every possible character you could acquire within a single playthrough. Then there were just the few stragglers that you could only get through subsequent playthroughs. I only missed people I had to, such as the viper manor scenario.

I haven't played through 3 times. I imagine I might as the years go on, so I figure "eh, I'll get them on the next playthrough".

It helps that new game + has a fast forward function when you're walking. I got Nikki in no time then stopped shortly afterwards(Guile was my first playthrough).