Единственно что прихдод на ум, это вот такой алгоритм.
Если таблица : users_view_topics с полями tid (id темы), date (последняя дата просмотра данной темы).
при просмотре списка тем сравнивать, если последний пост темы > последний визит юзера в данную тему, уведомлять о том что есть новые посты.
При просмотре темы, обновлять информацию в таблице users_view_topics;
Может есть более экономные для бд алгоритмы ?

писать в таблицу с темами дату последнего поста. и сравнивать по этой дате. (на дате, конечно, должен стоять ключ)
так же правильно было бы использовать тип таблиц InnoDB и в данном случае нужна транзакция, т.к. уже вырисовывается как минимум 2 связанных инсерта. т.е. один из них невозможен без другого.

тут подсчитать, если 100 юзеров, и около 1000тем := 100 x 1000 = 100 000 (в самом худшем случае).
других идей нет?

ну только если создавать еще таблицу и писать туда id пользователя и id непрочитанной темы.

а как отнесёшься к записям типа
`users` = '1,2,5,10';
в таблице с полями `tid` (id темы), `users` (id пользователей, просмотревших эту тему, через запятую (','));
а дата обновления темы берется прямо из таблицы тем

1) как ты собираешься в таком случае получать ID тем?
2) в любом случае, правильней было бы использовать сериализованный массив, а не id через запятую.

вероятно, пост N4 нужно исправить на "создавать еще таблицу и писать туда id пользователя и id прочитанной темы." думаю, так будет оптимально.
ставишь уникальный ключ на id пользователя и id темы и пишешь туда просто REPLACE INTO (userId, themeId, time) VALUES (1, 2, NOW());