Делая запросы через апи, сохраняем в самописном кэше id последнего полученного сообщения. Далее, при каждом вызове крона, получаем диалог с помощью messages.getHistory, где start_message_id = id_сообщения_из_кэша.
Затем помечаем диалог прочитанным (если нужно), добавляем сообщения в БД и обновляем наш кэш.
Если интересно, могу дать свой класс для работы с VK API. (Но и гуглится легко, просто делал очень лёгкую либу для себя)