Probably not the less resource intensive solution would be: Loop over all tags. For each tag, do a content/tree fetch with the objectrelationfilter (http://ez.no/community/contribs/template_plugins/objectrelationfilter) and a normal attribute filter on the published date.
Unfortunately a content/tree_count fetch does not support extended attribute filtering yet ( http://ez.no/bugs/view/8227 ). Otherwise that would be the preferred solution.
