Wenn der Timer Interrupt zu langsam ist, dann musst du es halt ohne den Interrupt machen. Also in einer Endlosschleife.

Wieso erzeugst du die 36kHz nicht mit einem anderen Bauteil und modulierst es dann mit einem Transistor, der an den uC angeschlossen wird?

Es gibt aber auch spezielle ICs für IR Übertragung. Damit dürfte es zuverlässiger funktionieren.