Short Answer
Your intuition is right - masses oscillate faster for a low wavelength wave because of greater distortion; it's just that in this case the wave also repeats faster in space...so phase velocity remains the same. If you like, mathematically, low $\lambda$ means low time period $\tau$ of oscillations of a particular point on the string, so that the phase velocity equal to $\lambda/\tau$ stays constant.
Extra Commentary
That the ratio $\omega/k=\lambda/\tau$ is completely independent of $k$ is not easy to answer a priori. What we can say is that high $k$ means more distortion, and hence a more violent normal mode operating at a higher frequency. How high $-$ i.e. proportional to $k^\alpha$ for which value of $\alpha$? That's impossible to claim without the exact formula for the potential energy of distortion. In this case small local length extension is given by $\frac{1}{2}(\frac{\partial y}{\partial x})^2$, which gives $\alpha = 2/2 = 1$.
Also, for a rope, the aforementioned approximation for the potential energy only works for small amplitudes, and for every amplitude there is a UV cut-off (for $k$) in-built in this system, beyond which the approximation breaks down and/or the rope breaks.
Dimensional Analysis
Another heuristic insight is dimensional analysis, which is the next best thing to a field Lagrangian. The only dimensionless combination one can construct in this case is $\omega/ck$, where $c = \sqrt{T/\text{mass density}}$. However, this is assuming the system supports waves and that $T$, mass density are the only relevant physical parameters (case in point: nobody knew vacuum supports EM waves until Maxwell & Hertz found them. Incidentally, this also happens to be an example of dispersionless waves across a very wide range of the EM spectrum as far as we can tell).
Edit
After-thought: A complete, slick and rigorous proof
I realized this cute argument while answering this question on stackexchange. The usual wave equation is invariant under Lorentz transformations in which $c$ is equal to the speed of the wave. While this procedure is purely mathematical and doesn't carry a physical interpretation in terms of frames with it in this case, one can still do it and argue that that $(\omega, k)$ transforms like the relativistic four-vector (two vector in 1+1 D) under these transformations, implying $\omega^2-k^2$ is a constant. Using the fact that Goldstone's theorem predicts massless modes, we've $\omega \to 0$ as $k \to 0$, implying that $\omega^2-k^2$ is actually equal to zero (this means we're relying on the existence of "Lorentz transformations" that can produce arbitrary red-shifts, making $k$ as small as we like)!