Hi Rob, just a remark:
In my private opinion it would make more sense to invest resources into impementing a formula reference which points to expanded formula cells (/edit/fill) like it is already done for formatting templates within the sheet. A slow sheet doesn't necessarily mean that calculation is slow. Better resolving references within the sheet (in my opinion) has more potential to make such documents faster. I believe by using formula references the documents' memory footprint could be lowered as well because a formula reference doesn't cost as much as a cell content containing a formula and containing edit engine data.
At one of the OOo conferences I vaguely remember there was a university project that already parallelized computation of Calc sheets. Unfortunately I cannot remember the project/university name anymore. Probably having a look at the conference session drafts might give us some more insight.
I was talking to someone earlier who had ideas for speeding up spreadsheet computation through parallelization, and was looking for some notoriously slow test documents.
Kind regards, Joost