I'm not 100% sure, but it seems like a bug in magento's built-in implementation of hole-punching for up-sell/related products.
I looked through the code and found that container for upsell/related products depends on customer session, but not on the currently viewed product.
Class responsible for upsell/related products caching called
Enterprise_PageCache_Model_Container_CatalogProductList and it extends
Enterprise_PageCache_Model_Container_Advanced_Quote. This class (CatalogProductList) doesn't overwrite neither
_getAdditionalCacheId methods. Thus this cache only depends on customer's session and because of that whenever any visitor visits the product page, which is not in the cache yet, magento rebuilds upsells block for that particular product and after that it is used on every product page for this customer.
As a temporary solution, I added below method into CatalogProductList class, and it fixed the issue. I know this is poor solution and I'm going to change that, but I wanted to ask if anybody had such issue and what is the solution for it.
Method which was added is
public function applyWithoutApp(&$content)