Это не проблема для IMAP.
Смотри
спецификацию, раздел SEARCH. Клиенты, использующие IMAP, однозначно должны уметь им пользоваться. Более того, система команд IMAP позволяет делать сложную выборку сообщений с почтового сервера — вплоть до писем от определенного отправителя во всех папках за любой промежуток времени.
