I'm not sure how pushing out of last is necessarily much more difficult if your medic can't run fast. The one play that's not nearly as viable is just popping through a choke immediately/jumping a demo through and catching up with a scout, I agree, but besides that I don't think the medic speed is that crucial in the push out. If you take it slow the enemy team is able to put up less resistance since their medic can't play as close as he currently can, which makes a slower type of push-out even easier as it currently is. It's a change in how you play the situation, but not one I think necessarily leads to more stalemates.
I think the general notion of 'medic can survive almost every mid as long as he just zooms out with a scout' has a big impact on stalemates though, since winning a mid semi-convincingly means you avoid the dreaded 100% uber on their last stalemate you get all the time now.