Same thing happened to me a year ago. Made a ressie using an e-cert. Process went thru, remaining amount CC charged. But e-ticket never generated, PNR and any trace of the ressie gone.

Called UA, the agents couldnt find anything by any reference. Thought I was crazy, agents thought I was crazy as well.

Eventually found the "e-cert" desk, or something like that and called there and they were able to trace the e-cert and where it was used and low and behold, there was the PNR just like you said above. From that point looks like that same lady had the power not only to restore the e-cert, rebook it at the original price at the time of reservation, but also ticket it in one call.

She said it was an e-cert computer issue that was well known to her but not widely known by her Reservation agent colleagues. It doesnt happen all the time but it happens. And the only way to prove that you are not losing your mind is to trace the ressie from the e-cert that was used. No one cares if you have the PNR, or a pre-auth on you CC, or even if you have a confirmation e-mail from UA.