Huh.

First Zodiac: Started with 2k Soldiery, ended up needing 1k Soldiery to finish my quests after getting all the dungeon items.

Second Zodiac: Started with 1600 Soldiery, have bought my 4th spring water and still have 7 dungeons to go.

These without overtly farming new people for soldiery bonus either time... Go figure.