I don't know how I got into grad school --- looking at the qualifications the incoming students have these days I don't think I'd make it --- and I only started my PhD 4 years ago.
This ratcheting up in qualifications is happening at every level in academia (and not just in CS). I know some grad students whose work and lifestyle is best described as "tenure track professors in the 80s." I know researchers at top labs like MSR who were hired on the strength of a _single_ OSDI publication. I had one as a second year PhD student, and I'm so far off the ball that I don't think I will even be attempting to go on the academic job market when I graduate. At this point I think it's pretty fruitless to apply to do a PhD without having prior research experience, ideally with a publication. I may be getting too jaded and pessimistic though. Consider alternate points of view.
On the other hand, if you can get in, it's a pretty amazing life of learning and developing industry relevant skills (if you're smart about it) on the NSF's dime. I know some of y'all are cynical about academia and like to badmouth PhD students as being unhirable and writing crap code, but consider that RTM is a top academic, and is pretty relevant as far as the startup scene is considered.