Buenas.
Lo que comentás es completamente cierto y existe, tanto en C como en ASM.
Esas 35 instrucciones que comentas son seguramente las que guardan los registros clave(como el W,STATUS,FSR...) y hacen la selección de cuál interrupción se produjo. Voy a destacar que en ASM bajo ciertas condiciones y truquillos es posible achicar bastante ese número de instrucciones. En el caso de un compilador ya no es tan sencillo ya que deberías modificar el ASM de salida a mano para lograrlo.
Las importantes son las instrucciones antes de ser atendida una interr. y no las que tarda en salir de la ISR(al menos para los Timers con tiempos medianos o grandes). A esto lo digo porque no interesa si tarda 10 o 100 instrucciones antes de salir de la ISR, ya que el Timer estará contando igualmente aunque se encuentre dentro de la ISR. Obviamente supongo que estará más que sobreentendido que no es necesario que el uC se encuentre fuera de la ISR para que un timer cuente

.
Ahora, si nos vamos a poner en exquisitos hay muchísimos factores a considerar. Ya han mencionado varios: los 2 ciclos de ejecución durante los cuales el timer no se incrementa cuando se carga un valor en su registro, las instrucciones antes de llegar a realmente precargar el timer y otras que no se han comentado como, por ejemplo, cuando se produce una interrupción, el uC automáticamente carga el vector 0x004(en el pic que exponés, 12F683) y eso lleva 2 ciclos de instrucción(es una especie de "call 0x004"). Además, puede que la interrupción tarde en producirse un poco más entre que el Timer se desborda y el uC realmente se percata de esto(CREO que son 2 ciclos más en el caso del TMR0). Dependiendo del tipo de interrupción, el uC puede tardar más en detectarla. Por ejemplo, una interrupción por cambio de estado del puerto b(RB4-RB7) lleva entre 3 y 4 ciclos de ejecución antes de que el uC se percate de que realmente se produjo y efectivice la interrupción.
En definitiva: lo que necesitás sencillamente es agregar a la formulita un numerito más que represente todos esos ciclos adicionales que hay que contemplar según la interrupción(y según lo que al compilador le de la gana (que es un verdadero trastorno, ya que también depende de su versión)).
Tiempo de desbordamiento = [(256-TMR0) * PREESCALER + A+ 4 + B] * (4/FOSC)
A= 2 si es que hay precarga del TMR0
B= número de instrucciones antes de que se se precargue el TMR0
Los cuatro ciclos adicionales correspondes 2 al tiempo de sincronísmo entre los relojes del uC, y dos más del call 0x004. Tal vez eso demuestre la incongruencia entre tus cálculos teóricos iniciales y los del programita que usabas para calcularlos.
Si no se precarga el registro TMR0, A no exíste y B no tiene importancia(se ignora).
Saludos.