Look at Gungrave, GetBackers, and Naruto. The majority of the characters typically come from a central hub, whether it's slums, a towering sanctum, or a large nation in the middle of several other warring nations. I would guess that for any one character who's origin wasn't immediately implied in the game, wherever they were is where they were from.

You know, for most games, it's the origins and the pasts that are already mentioned and the children who exist that have always made me wish for more. But with VII's lack-thereof, there was actually plenty excuse to continue VII with a compilation and maybe even a remake.