I'm actually working on a project with similar requirements to yours -- I'm building a GPS-disciplined NTP server on an Arduino (not for any serious industrial need, just to see how good of a job I can do), so of course the core of it is an adjustable timekeeping loop using one of the AVR's hardware timers.
I decided to leave alone the TIMER0 which is used by the arduino library's micros() etc. and instead programmed TIMER4 myself (I've got a Mega2560 board, which has the ICP4 pin routed but not ICP1; a 2009 should work as well if everything is changed over to use TIMER1, since that board has ICP1 routed but there is no ICP4). It pre-divides the 16MHz clock by 8 for 0.5uS counter resolution, and uses a timer overflow value of (nominally) 62500 to give 32 interrupts per second. By varying that value +/- 127, I can get +/- 2048 ppm speed adjustment in units of 16 ppm, but by dithering I'm able to make the adjustment accurate to +/- 1 ppm over a period of 0.5 sec and +/- 1/16 ppm over a period of 8 sec.
Coupled to that is a PLL that locks to a 1PPS input signal connected to the ICP4 pin (substitute ICP1 for the 2009), and the code is able to timestamp events on the input capture pin as well as read the current time from the counter.
Consistent with what you saw, I observed about a 24uS jitter associated with having another interrupt delayed by my timer ISR. Using the input capture pin can mitigate this, but since there's only one ICP per timer, you'd need to multiplex it cleverly if you wanted to use it for external events and
for locking to the 1PPS.
consistent with what you saw, the crystal on my board runs about 240ppm fast at room temperature, and it's very
temperature-sensitive, with a constant of about 15ppm/degC. I've got a 1-wire temperature probe wired up and taped to the crystal, and I'm working on putting temperature compensation ahead of the PLL, but it's a little bit fiddly and I haven't finished with that yet.
My code is admittedly fairly scary and I haven't reached the point where I was ready to show it to the world yet, and the PLL is really ham-fisted because this is NOT my specialty, but if you want to have a look at any of it, it can be found at http://cleverdomain.org/git/arduino/HEAD/tree