Пишу почтовый клиент.
Письма хранятся на сервере и с сервера не удаляются.
Хочу при проверке почты загружать с сервера на клиент только ранее не загруженные письма.

Теоритически, имеется команда UIDL, благодаря ей все сообщения, хранящиеся на сервере, получают уникальные номера, которые можно использовать для обнаружения новых писем.
Проверяю на Office Mail Server 0.7.26 , UIDL выдаёт НЕ уникальные UID для части писем. При этом, например, The Bat! эти письма с не уникальным UID получает нормально, т.е., по видимому, The Bat!, при проверке почты на сервере, проверяет ещё какую то информацию, но он проверку сервера на наличие новых сообщений проводит очень быстро, т.е., скорее всего, перебором всех сообщений не занимается. Как он это делает?

Видимо клиенты используют вместе с командой UIDL команду LIST и получают кроме UID письма ещё и его размер. Обе команды довольно шустро выполняются.
Но всё равно остаётся вопрос, как быстро найти новые письма. Перебирать все когда-либо загруженные письма очень долго.

Ну вот в логах POP3 сессии как раз ничего интересного нет. Из лога видно, что клиент собирает UIDы и размеры писем: Например у меня на одном из почтовых ящиков 501 письмо лежит на сервере и 500 лежит на клиенте. Соответственно, для того, чтобы проверить какое из писем на сервере новое, клиенту необходимо сравнить 500 писем с сервера с 500 письмами клиента. Это довольно долго должно быть.

Проверил, перебирает действительно довольно быстро. Кажется вопрос исчерпан.