Don't rely on the MUXout or LD out of a PLL synth compared to rising edges of data input to give you accurate lock time measurements. The LD lines tend to go high well before the final freuqency has settled to, say, within 1KHz of final freq. The only accurate method is a tranisent mode using an SSA. ...
Never underestimate the feasability of overdriving VCO Vtune. Check your datasheet of course, but to cover there own asses component manufactuers always give lower and upper headroom in addition to AMR's.