The relative stability of Sc, Ti, and V encapsulating Ge-n clusters in the size range n = 14-20 has been studied through first-principles electronic structure calculations based on density functional theory. Variations of the embedding energy, gap between the highest occupied and the lowest occupied molecular orbitals, ionization potential, vertical detachment energy, and electron affinity with cluster size have been calculated to identify clusters with enhanced stability. The enhanced stability of some clusters can be very well explained as due to the formation of a filled shell free-electron gas inside the Ge cages. For the first time, direct evidence of the formation of a free-electron gas is also presented. In some other clusters, enhanced stability is found to originate from geometric effects. Some clusters that may be expected to have enhanced stability from simple electron counting rules do not show that. These results provide new insights into the long-standing question of whether electron counting rules can explain the relative stability of transition metal encapsulated semiconductor clusters and show that these clusters are too complex for such simple generalizations.