I found I was able to reproduce the "non lock" with an eval board, and I have a theory of what is happening
Looking closer at the datasheet of the ADF4351, it seems that "programming the registers" does more than just load values it it, a number of circuit selections happen inside the chip while the programming process is happening. This is why the registers must be programmed in a certain sequence: R5, then R4, then R3, ... last R0.
If there is no reference frequency during the process then it will fail.
If you power-up the adf4351 with a reference, then remove it, then connect it again, the PLL will lock. The problem is if the PLL is that if the PLL is programmed when the reference frequency is missing, the programming doesn't seem to work.
My suggestion would be to make sure that your programming includes correct programming of the Lock Detect output, then change the programming of the 12F675 so that after programming you wait a bit, wait for Lock Detect to go active, and if not, re-start the programming process. I have not tried it, but your "touch the MCLR" suggest this will work.
I'm nervous about the "touch MCLR" comment. Does this pin have a pull-up resistor?