But that doesn't work for the regular troops of Gondor.
Are you actually stating that those troops are basically only level 2? They fight more creatures on a monthly basis than most players fight in their first 5 levels...
In AD&D I'd make them probably F2, in 3e F3 or maybe War-4 (I might eg use F3 for cavalry, for Faramir's men, and War-4 for regular infantry). I don't give a damn about the PHB XP table, that is for measuring the rate of Player Character progression and is irrelevant for NPCs. What matters is their capability. They are not PCs and should never be thought of as such. YMMV.