In my /var/log/mail.log I saw the following error:
Aug 6 17:12:58 Nephtys cyrus/imap: SQUAT failed
In order to fix this execute the following commands:
# sudo su cyrus
This will make you the cyrus user.
This will index all your e-mails (more info by executing $ man squatter). This index is not incremental so you need to run this task once in a while. It might be usefull to create a cronjob for this command.