Yes, the localized-categories plugin has the same issue with anonymous caching.
It’s possible to extract the desired locale from accept-language header before adding it to the cache_key. That way the cache isn’t be broken for every possible accept-language header. It’s also unlikely that any site would need more than 2 or 3 languages. If a forum’s supported locales were set as a global setting, those suupported locales could be compared agaist the locale extracted from the accept-language header. The cache_key would only need to be updated if the locale extracted from the accept-language header matched one of the site’s supported locales.
This might still be too inefficient, but not as bad as busting the cache for every possible locale.