mi sa, che memorizza il link nella cache di explorer quindi anche se entri con un'altro id dallo stesso computer dovrebbe essere ancora visited
potresti usare una soluzione complessa... fare 2 css uno con lo stato visited = a quello con lo status de visitare e uno con lo stato visited normale...
poi controlli se l'utente accede per la prima volta alla pagina web e fai usi il css appropriato...
Se non sono stato chiaro ripeto...