Some time ago Mike Keitz posted info about a PIC pll that was designed to
lock to HSYNC of an NTSC signal. His approach was to vary the pic's clock
frequency using the variable capacitance of a reversed biased diode. IIRC,
the diode provided some of the capacitance of a resonator circuit. I don't
see why this approach wouldn't work here as well. I'm not sure how your
feedback circuitry is implemented. In other words, does the signal you
generate get compared to something else to create feedback control (e.g.
like Mike's HSYNC) or is it generated as an absolute (e.g. something tells
your system to spit out a square wave with a xx kHz frequency). If it's
the former then you'll obviously need the conditioning circuitry to convey
the error to the pic.  If it's the latter then you'll need a reference
clock source to which you can compare your generated signal. This is
analogous to the DDS solutions others have discussed.

Perhaps Mike could explain the concept more clearly (or repost that old
message). But as I recall, he varied the control voltage on the diode by
creating a bit-banged pwm signal that was averaged with an RC circuit. The
RC circuit's time constant was much slower than the HSYNC frequency. Every
time an HSYNC edge came in, the pic would compare it to when it 'expected'
the HSYNC to occur. If the expected edge was too fast then the pic was
slowed down by making the PWM output low. If the expected edge was too
slow then the PMW output was made high. Pretty damn clever.

Scott