One of the dangers of allowing statically generated tag archives is how big they can become. I'm trying to avoid that in the default template by having each tag confined to its own page, and thus regenerating only the pages where the tags are changed. Rebuilding them in the background may also help speed things up.
I'm also contemplating a timeout value for queued actions so that if a given page takes a very long time to process, the queue will automatically break there for a fresh iteration so that the client's status can be updated. This would be useful for dealing with long-running pages like tag archives.
Another easy speedup would be to have tag archives in the default templates broken up by year -- e.g., /tag_name/year, and allowing pagination of some kind between them. That would further limit the amount of rebuilding going on, but only for that particular template (or theme).