test conditions: on my VPS, a bitcoind patched to ignore the dust filtering and free relay limiting, and sending a "mempool" to every peer at connect time, waited until poolsz >5000, then measure getblocktemplate RPC latency. Result: 10-20s without this patch, 0.5-0.7s with this patch.

EDIT: up to 1.0-1.5s after running for several hours (poolsz still ~5000).

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/2ec349bc420d7f4541bf91acf8b830377a1421f3 for binaries and test log.
This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/
Contact BlueMatt on freenode if something looks broken.

I'm not familiar enough with the code and the template structure to know what is possible so please bear with my uneducated suggestion.

Would it make sense to have part of the template being computed asynchronously?
Have a thread wake up regularly and build a base structure with a snapshot of the tx available. When a call to getblocktemplate or other RPC functions scaling in o(nb_tx) or worse is done, use the precomputed structure instead of the available tx. When a new block is known update the structure right away and/or swap with a temporary "quick to compute/0 tx" one until the thread can catch up and build one with available tx.
I see params of getblocktemplate that obviously won't allow using this optimization (passing the transactions for the most obvious) but my lack of knowledge of the actual template format and build process makes me wonder what other params could prevent this kind of optimization to be useful. At least it seems to me that with no params the optimization should work and allow for o(1) scaling for getblocktemplate. In the end my suggestion only makes sense if most pools could benefit from it and aren't forced to use params that prevent it from being useful.

@gyver Thats what miner software should and (some) does do. .. but at some point you need to compute the data... and it's good if it's not a slow and expensive operation.

ACK

@gmaxwell of course I agree speeding up the actual computation is desirable.

I was wondering if it wouldn't make sense to implement this async technique in bitcoind itself. For example I suspect (again: uninformed guess) that slow calls to getmininginfo and getblocktemplate use the same access pattern to an internal tx structure and could benefit from the same optimization (at least they became slow on my node when the number of tx started to grow). At some point when multiple tools all implement the same algorithm on top of another tool the question of integrating this algorithm in the common tool becomes valid (the answer isn't always obvious though).
It could become more obvious when the heavy client only makes sense for pool owners/miners (and most end-users have migrated to lightweight clients).

It's just an idea to test the waters (mainly to avoid wasting time with it if the template build process intrinsically can't benefit from this approach), it's far from a feature request.

I'm more and more interested by the node's source code and how I could play with it but I just scraped the surface...

@gmaxwell still thinking about your suggestion and focusing on how miner software can optimize their latency when a new block is accepted by the local node. The miner doesn't want to use an old cached template to avoid wasting work but can't simply call getblocktemplate naively if it wants a fast reply (event after a new block there can be and often is a lot of transactions to include in a template).
It can receive a notification from the node (there are already interfaces for that). I assume that to minimize latency it can call getblocktemplate with an emplty tx list to get a fast reply and immediately call it again without specifying the list to include txs as soon as possible.
As many pools have closed source software I'm not sure if they really implement this kind of behaviour. Latency issues may be solved by simply publishing recommendations for miner software instead of modifying bitcoind itself. As p2pool is probably the most likely to benefit from this, I'll link this post in the p2pool bitcointalk.org thread and continue there to avoid deviating even more from the subject here.

@gyver Eloipool is free software an implements the optimizations you appear to be describing there. (precomputed empty templates and such).

@gmaxwell thanks for the pointer. Was already in my large bag of source code to read but moved near the top of the pile :)