I managed to make some progress with the temporary obstacle handling. Most of the required pieces are now in place, next up is bunch of massaging to make it great.
So the stuff I have working now is a preprocess step which rasterizes the tiles, creates a minimal representation of the heightfield and then "zips" it. These data chunks are stored in tile cache. Upon request tile cache will create a piece of navmesh for you which includes all the temporary obstacles too.
I use tile size of 48x48 in the video. It takes about 2 ms to update one tile. So in worst case adding one obstacle takes 8 ms. Interestingly the conversion from the minimal representation to compact heightfield takes about 25% of the time, and generating detail mesh takes another 25% of the time.
For those in dire need for the extra nanoseconds, I think I'll provide dummy detail mesh generation process which just triangulates the polygons instead of trying to add more detail. Or maybe even support that at runtime like in the old days.
Apart from the few offenders, each Recast call takes very little time, so it is possible to timeslice the generation.