Taxonomy term not getting invalidated
Yes, the invalidation is automatic. From the debugging you have done so far you only know that the tag is somewhere on the page, but you don't know where it is and obviously it is not where you want it to be. Look in the database table cache_render. Clear the cache, so that it is emptied. Now request the page with the block and check for all cached elements the column tags.

By the way, you don't need to set cache keys on a block, because blocks do this automatically and for the problem here it's confusing, because the taxonomy id you set in the keys is not invalidated.