Если вкратце - определил, что проблема не в коде. Проблема в том что сервер тг или сама библотека тупит.
Решение выбрал не самое лучшее, но рабочее.
А именно, вместо search_messages использовал get_chat_history. Программа при этом выполняет запрос всех сообщений и находит в них нужного юзера и его сообщения.
Не то, что я хотел, но по другому не работает. К сожалению. Также убедился в этом у модераторов pyrogram