Просто если каждый клиент будет проверять активность остальных не велика ли это нагрузка?

если правильно все сделать, то все будет пучком
по-крайней мере пока вы не собиретесь написать вконтакт-2
а)вам надо для колонки с последним моментом активности юзера в БД сделать индекс. Тогда операция удаления неактивных пользователей будет достаточно быстра
запрос можно оптимизировать до
DELETE FROM active_users ORDER BY last_time WHERE last_time<TIME()-20 LIMIT 1
также можно использовать какой-нибудь семафор(например файл), или запускать удаление по cron-у, и тем самым наверняка ограничть количество запросов на удаление, без потери результата

Спасибо, будем пробовать

А можно пойти по стопам Зива и Энди, и при каждом обращении (после выдачи результата) с вероятностью, скажем, 5%, удалять старые записи. А с вероятностью 1% делать OPTIMIZE TABLE.

Ну, как вариант исключительно :)

кто такие?

Разработчики PHP в том виде, в каком мы его знаем.
Подобным образом, с определенной вероятностью, пуржатся в пыхе мертвые сессии.

В MySql команда DELETE физически данные не удаляет, а только помечает на удаление. Не вижу проблем со скоростью особенно при выборке на индексе.
Удаляет физически - OPTIMIZE TABLE, ну и новые INSERT пишут свои данные поверх помеченных на удаление.
Так что с 1% Зив и Энди как всегда рулят.