I am about to prove once and for all just how geeky I am.
Vincent was indeed hidden in the Shinra Mansion in Nibelheim. You can get him the first time you visit there. Somewhere in the Mansion is a bit of paper with four clues on it (the last is in invisible ink) telling you that someone is locked away in the basement and by getting these four clues right, you’ll find the combination to open the safe and get the key to release him.
When you’ve got all four numbers, you open the safe and get attacked by a monster called Lost Number (don’t ask how i remember all this. I have no idea). He’s got one strong magical half that’s vulnerable to physical attacks and one strong physical half that’s vulnerable to magic. Eventually you’ll kill one half off and be left with the other. I found that the physical half is more likely to kill you, so soon as the whole battle begins, only use magic attacks to kill off the physical side and be left with the nice and easy magic one.
Once you’ve killed him completely, you’ll get a key and an Odin materia.
Go to the basement as per the storyline. Once you’re down there, there’s a screen with a long passageway leading up to the library. There’s a door there. Open it. Find Vincent. You’ll have to talk to him a couple of times though, until he just says “Leave me alone” or something similar. Do the whole Library / Sephiroth bit then come out and he’ll join you.