There's definitely a huge challenge when it comes to mods/admin control, and I agree that time-based seniority shouldn't be the way for the reasons you outlined.
I think engagement-based seniority is also a challenge, as it doesn't factor in the 'justness' of the engagement. For instance, a mod could downvote, put negative comments, or engage in other non-solution oriented ways and that still count as fulfilling their duties.
I think a combination of all three is a good way to go.
Imagine users vote on moderation outcomes as a way of reinforcing (or challenging) the legitimacy of the moderator - sort of like how people say 'Good Bot' on Reddit to reinforce that a bot is doing its job properly.
So a moderator's seniority could be determined by a metric derived from longevity, high engagement, and high community-reinforcement on moderation outcomes.
This could be abused by the community (negatively reinforce legitimate moderation outcomes in order to displace the moderator), however the solution would be that negative reinforcements against a moderator are flagged to the overarching Just About admin team. They could then view a sample of instances where the moderator intervened and determine whether there is a problem to be addressed.
