Använder de båda samma browser? Jag tänker mig att en slarvigt installerad browser i företagsmiljö kan ha sina cookie-filer på en delad yta, vilket skulle förklara hur de skriver över varandras kakor för din domän slumpmässigt.

Nyckeln är i detta fallet inte unikt.
Lägg till någon mer parameter som gör den unik. Tex. tid för inloggning mm.

@Perben: Något åt det hållet är vad jag misstänker. Förslag på hur man skulle kunna lösa det om så är fallet? Känns lite knivigt...

Kan det vara så enkelt som att de använder samma dator?

Nepp, det gör de inte.

Cookie-filen ligger på disk, och varje browser har sin specifika plats och namn. För Firefox t.ex så heter filen cookies.sqlite och brukar lägga sig under användarens hemkatalog om jag inte missminner mig.

Om så är fallet, och användarens hemkatalog är en nätverksresurs (vilket den ofta är), kolla om de inte är inloggade som samma användare... vore ju enkel lösning.