Refer to this post for a description of the feature.
My HTML cache is enabled, and I have turned on "Clear on Index Update" for one of my Renderings.
However, the entry for my Rendering is NOT marked with any special token in the cache - I verified the cache content before and after using the rendering. This, of course, leads to the Clear() method in Sitecore.ContentSearch.Maintenance.IndexDependentHtmlCacheManager to not pick it up, making this feature useless.
I am on Sitecore 7.2 - is this a known bug?
Ok, it turns out that this features is currently bugged on MVC, at least as of 16th of March 2015:
http://www.tarasalenin.com/caching-sitecore-mvc-renderings/
That's about it. There are workarounds, but in the meanwhile I sorted my problem in a different way. Posting this in case someone else happens to have the same problem.