No kidding. One of the party members, Geoffrey (who was a fighter and represented the virtue of Valor) is behind a locked door in a game where it's not entirely easy to buy keys to said doors.
My father, brother and I had the hardest time of finding the shepherd companion (Katrina). I think in the end we solved the problem by starting the game as a shepherd, which is basically "hard mode" as you have the weakest starting position (level 1 out of 8, whereas other starting characters begin at level 2 or 3), you can never use magic, and you start off on a small island near a ruined city.
Much later on, we found the damn shepherd, south of the starting point in said ruined city, entirely off of any road there.