This issue has been isolated to "old" content that was published prior to activating the output cache profile. New content (post cache activation) is not suffering from this.

I have a SharePoint 2010 publishing site on which I enabled a Public Internet - Purely anonymous cache profile. 

On each page, regardless of the content, the output cache is always regenerated (the debugging time is always changing to the current time, while my duration is set to 3600)

I carefully read everything that I was able to gather on the web, including this exhaustive article from Todd Carter : http://todd-carter.com/post/2012/01/31/When-Page-Output-Caching-Does-Not-Output.aspx

- I don't have >= 10.000 secured items in my site collection (only ~ 20) which would prevent the cache from working

- I don't have a cookie being added to the http response (I used to have but I removed them for debugging this issue)

- I'm accessing as an anonymous user so no other cookies (authentication,...) are added

Investigating in the ULS result in this pattern for all requests :

- Cache Hit for query Web - /ab/FR, ListName - Pages, Query - <Where><Contains><FieldRef Name="FileRef" /><Value Type="Url">/default.aspx</Value></Contains></Where>.
- Creating result set.
- Adding super user IDs.
- Adding Super Reader IDs.
- Content from SuperReaders and SuperUsers.  Merging.
- Enabling specified cache profile: XYZ - Public Internet (Anonymous)
- EnableCache: True  Duration: 3600  VaryByParam:   CheckForUpdates: False  CheckForRights: False

Which is thus lacking the 
VaryByCustom for url https://xyz
Calculating VaryByCustom for CachingEnabled.	
Calculating VaryByCustom for HostName.
Calculating VaryByCustom for HasWPCustomization.
Calculating VaryByCustom for AuthenticationVaryByCustom.
Calculating VaryByCustom for ConsoleVaryByCustom.
Calculating VaryByCustom for UserCanEdit.
Calculating VaryByCustom for Browser.
VaryByCustom for url xyz called with custom ...

The cache seems thus be hit but the content is always regenerated... (the varybyCustom seems to be used as the complete aggregated key)

Anyone got recommendation or advice to ensure the cache is used or to debug it even deeper ?

Many thanks.

PS : Single server farm for dev environment, thus no network load balancing. This issue was raised on a functional testing environment with 2 WFE / NLB but the problem was not there.