When you're designing a feedback circuit, you don't necessarily need the biggest gain from each component in the loop, just sufficient gain. More important than gain is stability. A good way to design an unstable system is to have several high gain stages, each rolling off at a similar frequency.
In the case of the old style regulators, enough gain comes from the differential amplifier. The common collector stage is fast, it has no Miller capacitance, which makes it easier to concentrate all the stabilisation efforts into the differential amplifier. But they are expensive in terms of a high minimum voltage drop across the part. 3v wasted was OK with 15v rails, but looks pretty sick with 5v and 3.3v rails.
Newer style LDO (low dropout regulators) do use a PNP common collector stage as the output device. They need a more complicated amplifier stage before them. Read the datasheet carefully before you use one, some are unstable into the 'wrong' sort of output capacitor (ceramic).