(I'm not suggesting that you need to wait indefinitely for well-earned rewards, of course. It's just that I've seen a lot of "thinks they're higher-performing and delivering more value than they are" than the reverse.)
My longest engagement is about 2.5 years. The average length is probably around 20 months. I've left every position by my own choice and to the dismay of my employer. I'm not trying to boast, but it's clear from my evals, references, and repeat business I've received since being independent that I was and am highly valued. Each job change came for a different reason (family/personal, wanting more responsibility, etc.) and was not premeditated when I took the job. I can't say for certain of course, but I have no reason to believe any of those employers regret hiring me. You can be incredibly productive and a contributor over a period of 1.5 years. In our business that's a long time.
On the other side of the coin, I've worked with many mediocre performers who, due to lack of options, have recorded long stints at reputable companies. In my experience, for people to get let go, they need to be exceptionally bad. Average people stick around a long time. That's why I think using duration as a marker is double-sided. As you mentioned, promotions can be a good marker to offset this effect.
Previous job longevity is worth next to nothing without talking to the candidate in my opinion.