If the URL contains Unicode characters, WP Super Cache seems to get confused and not delete the cache when a comment gets posted.
A specific example is the single-quote (') character. If someone copies the character from Word, it comes across as a UTF-8 URL encoded %E2%80%99 in the URL/permalink. This plugin seems to be REALLY confused. There are four directories. One directory is named as the Unicode version but there are three expanded versions: %E2%80%99, %25E2%2580%2599, and %2525E2%252580%252599. URL encoding already URL encoded strings for the win! This, of course, explains why the caching system is breaking.
This is happening on a multisite WP 3.0.4 setup. There are several custom-built plugins that I wrote in use but shouldn't be affecting anything involving WP Super Cache.