I made a patched version of 0.5.6 for our own personal use, which does nothing except make those parameters configurable.
The performance cost is noticeable; setting them to 8/4, it goes from 0.4ms to 1.5ms per tick. At the same time, it completely fixes the unresponsiveness. That's fine for our case, but it obviously can't be the default. OTOH, I note that the cost only jumps that way when there are unachievable commands set -- deconstructing unreachable fish, for example, or cliffs.
It seems you already differentiate between new commands and old ones, iterating through the older ones at a slower pace, but I'm not sure of that. Still, I think one possible fix would be to make the system more dynamic -- keep track of how old a ghost/decon/whatever command is, put them in exponentially increasing buckets and only iterate over e.g. the 32-64 tick bucket once every 32-64 ticks.
In principle. You'd need to spread the load out per-tick to avoid super-heavy ticks, the way you're already doing.