Как работают современные мессенджеры?
как сервер за столь короткое время умеет прошерстить базу данных, найти сообщения конкретного пользователя и отдать их
Я бы делал немного иначе, например пользователь отправляет сообщение, которое принимает сервер.
В случае, если получатель сообщения также подключен - сервер параллельно доставляет получателю сообщение, за счёт этого имеем быструю доставку сообщений, и параллельно сохраняет сообщение в базу.

Что касается быстрой загрузки истории сообщений - то тут нужно сохранять сообщения таким образом, чтобы сообщения одного пользователя всегда были на одном и том же сервере (если используется шардинг). Тогда обычный SELECT из базы по user_id будет вполне себе быстро работать даже на огромной базе. Также таблицы можно еще партицировать, чтобы еще быстрее загружать последние сообщения в истории.

Что касается безопасности, если не использовать e2e шифрование, как вариант, можно использовать обычные RSA ключи. Например на сервере генерируем два ключа, открытый отправляем кленту, он шифрует им сообщение и передает сообщение на сервер. Вы на сервере его расшифровываете при помощи закрытого ключа. Для отправки сообщения клиенту, можно сделать тоже самое. Клиент также генерирует два RSA ключа и открытый ключ отправляет серверу. Когда  серверу нужно доставить сообщение клиенту, он шифрует сообщение открытым ключём, который ему высылал клиент и отправляет ему.

Мне тоже интересно узнать другие варианты решения этой задачи, буду следить за этой темой :)

Хорошее дополнение по хранению сообщения и организации поиска от Ильи
Распределение нагрузки решается шардингом — получается много небольших БД вместо одной огромной. Скорее всего каждое сообщение разбивается по словам/частям слов и сохраняется в поисковый индекс типа слово—message_id и такой индекс строится для каждого пользователя и тоже шардируется. При поиске сначала получаем идентификаторы подходящих сообщений из поискового индекса, потом выгружаем сообщения из БД с сообщениями.

Дополнение от Stalker_RED 
только не "сообщения одного пользователя всегда были на одном и том же сервере" а сообщения из одного чата/канала/группы (включая чаты, в котором всего два участника). То-же самое касается построения индекса.
не могу понять, как сервер за столь короткое время умеет прошерстить базу данных, найти сообщения конкретного пользователя и отдать их. 

select по id самый быстрый, в любых БД, что именно Вам непонятно?
он же не в один чат компонует, приложуха запрашивает столько чатов сколько нужно