А что тут еще можно придумать? Выбирете все сообщения, относящиеся к нужному топику и со временем, старше времени последней активности пользователя в этом топике (или на сайте вообще). При нормальной модели данных, при наличии индексов — всё будет работать.
Да и «кол-во записей в бд» знаете ли, зависит от задач — кому-то 100 000 уже много, а другому и 10 млн нормально. Маловато подробностей…