Massive template cache cleaning tasks always get stuck
As suggested by Fred, using the {% cache globally using key craft.request.path %} trick from https://craftcms.stackexchange.com/a/8335/342 gets rid of almost all duplicates!

But for the last few I notice that the duplicates all expire within seconds of each other, maybe this is an instance of https://en.wikipedia.org/wiki/Cache_stampede ? 

I.e. several clients request the pages "simultaneously" and the page is rendered several times, and each version is cached?