Проблема решена.
Команда SEARCH не всегда работает корректно с (FROM "no_reply@example.com"). Помогло разделение элементов запроса:
typ, edata = connection.uid('SEARCH', None, 'FROM', 'no_reply')
Причем полный адрес no_reply@example.com также не ищет входящие письма.