Cannot invalidate template cache (by element) on entries.onDeleteEntry
Ok so here's what did it:
In my plugin, I had to manually call:

        craft()-&gt;templateCache-&gt;includeElementInTemplateCaches($entry-&gt;id);


With that, I didn't need had any of my event listeners in place.

Interesting that things seem to be inserted into craft_templatecachecriteria automatically, but not into craft_templatecacheelements...Perhaps that is bug?