A maneira como faço isso é pingar periodicamente um manipulador especial usando AJAX (uma vez em 30 segundos). São muitas solicitações, então, em vez de atualizar a tabela de usuários online toda vez com a última visita, estou atualizando o memcache. Eu só atualizo o registro do banco de dados quando está 5 minutos atrás do registro do memcache (você pode escolher um atraso maior ou menor dependendo da carga). Em seguida, um cron job remove os registros obsoletos da tabela de usuários online.

Para verificar se um usuário específico está online, basta verificar seu registro de memcache. O erro nunca é superior a 30 segundos. O banco de dados nunca está mais de 5 minutos atrasado, então os resultados do banco de dados também são bastante precisos.

Eu também uso essas solicitações periódicas para enviar eventos para o usuário.