I agree, mostly. A possible route is to do a Master's at a mid-tier school, making sure to do research that results in a publication. That turns you into a very strong candidate and a mid-tier Master's program is easier to get into. And you might decide to stay at that school for a PhD!
This is exactly what happened for me. I started an MSCS at a decent state school, took an elective course in cryptography and crushed it, and the professor basically propositioned me to switch to a PhD and fast-tracked my application. Nothing else on my weird-ass mid-career resume mattered, because I took his course and he had all the evidence he needed.
