The problem of vanishing gradients is basically that since our step size is proportional to the gradient, if the gradient is very small, it might take a long time to reach a local minimum. So why don't we just not take our step size to be proportional to the gradient, and instead do a line search?
The intuition for why gradient descent ought to work is just that if we move in the direction of steepest descent, it should tend to make the function smaller. However, it's not obvious why the step-size should have to be proportional to the magnitude of the gradient. In an old paper on the subject, Haskell shows that gradient descent converges so long as we do a line search, he doesn't consider the case of proportional step size. The more I think about it, the less good reason I see at all why taking the step size to be proportional to the gradient should be considered a good or natural way to do gradient descent.