Honestly why would you make this complicated system, when my suggested system is much easier to the players and to the devs?
When you're on almost zero stamina, wouldn't it be just annoying when you're trying to climb a voxel but that takes almost a second? It wouldn't even feel like climbing nor stepping, it would feel like shuffling along in mud. You shouldn't climb, you say? Well since this is automatic, it'd be quite hard to avoid. And even if you moved back, it would still take ridiculously lot of time.
It would be hellish if you had just autoclimbed a hill, but now you can't hop over a 2 voxels high wall because you have no enough stamina left, and enemy gets you. Would that add any fun, strategy or excitement?
It would be hellish if you are just averagely running and you need to stop to regain stamina.. in the middle of nothing?
Would you want to force the player to go away crouching?
And even Gorman's suggestion about acceleration/deceleration isn't as simple as it seems to be in the first glance, although it is fairly better than rulefiron's one.
slow you down to half speed after 5 autoclimbs.
So again, walking in mud.