Not saying you're incorrect, but I know that my third-gen Verizon iPad uses LTE and does not have this issue. It would be strange that the LTE iPad would use a different server than the LTE iPhone, I would think.
To me, it almost seems like the iPhone 5 is trying to handshake with the LTE tower(s) and it's trying two or three different protocols or something and then it finally finds the one the tower is talking on and the connection is established. I have no idea how LTE works -- this is just a layman's idea.
I've also noticed that it takes about 10 seconds for my iPhone to lock onto an LTE signal when it's powered on. My other theory is that the LTE radio is programmed to turn off when the phone is locked to save battery; and when the phone is unlocked, it's basically having to find the signal and lock on all over again. Two issues with this idea though: the problem isn't affecting everyone with iPhone 5 handsets, and the phone doesn't say "Searching..." when you unlock it like it does when it's powered on. In fact, in every case I've had this problem, I've had full LTE signal strength while the problem is occurring.