I did all the quests in every area too. (this was probably a mistake, but I like being level capped for quests, rather than the min level) As far as fates go.. I never just sat and camped them, or ran around looking for them if I ran across one I'd do it. I exp partied, or soloed maybe 3 levels above level 20. I just got the achievement for 50k seals, and that's with doing 2 company logs so that should give you some idea of how many fates. I've done Savra maybe 8 times?