We're forgetting something.
The blink happened thousands of years ago. Just like Alice has been around all that time, Mr. Church has to have been too. And he certainly wasn't under Pate's control all that time.
This suggests two possibilities:
1.) Church has some limitation or throttling that compels him to either have a master or need to collaborate to accomplish what he wants to accomplish, and moves from partnership to partnership as the other parties age/die, or
2.) Pate came into possession of him somehow. For example, maybe he was deactivated and stored, and Pate discovered him, and was able to adjust his programming in some way before activating him.
I like possibility #2. It also fits well with Pate's archaeological endeavors. I'll bet he's found more than a couple interesting and useful curiosities.