Inspirado pelo comentário de Michael Hampton, eu cavei mais fundo.
Isso me fez perceber que o W3 Total Cache é provavelmente o responsável pelos links aleatórios do cache em uma base por usuário.
Nas configurações do plug-in do W3TC, adicionei "aleatório" (sem aspas) à "Lista de exceções do cache" na página de configuração do cache de páginas (/wp-admin/admin.php?page=w3tc_pgcache)
Obrigado pela ótima pergunta que levou à descoberta da resposta, Michael.