Finalmente encontramos o problema (mais ou menos).
Em certas combinações de SO do cliente, versões do Citrix e TS OS 'combinadas com versões do Adobe Reader (mas possivelmente de outros programas), você pode experimentar isso.
Sendo que a Citrix acredita que fechou o programa, mas na realidade ainda é executado sob o usuário no TS. Essa situação leva a mais instâncias do Reader sendo gerado (desde que ele não seja executado ...) quando um usuário abre um PDF. Nenhuma das quais se torna visível para o usuário.
Não sabemos exatamente onde está a falha, mas sabemos agora com certeza o que a causa, e é fácil evitar. Se o usuário fecha o Adobe Reader (ou um grupo de aplicativos Citrix) usando o botão direito do mouse na barra de tarefas, em muitos casos (achamos que nem sempre) a Citrix acha que fechou o Reader, mas o Reader ainda será executado e você tem a situação.
Resolvemos isso simplesmente instruindo nossos usuários a não fecharem programas dessa maneira, e se eles entrarem nessa situação, eles poderão fazer logout e voltar novamente, e todas as instâncias do Reader terão se fechado.
Eu escrevo isso aqui porque eu e meus colegas passamos horas e horas tentando chegar a isso.
Obrigado a todos que responderam!
PS: Leia a minha pergunta para mais informações.