Most IMAP servers support "next unique ID" feature which makes it possible to retrieve a unique ID to be assigned to the next message to arrive. When a message arrives, this value changes, which makes it possible to use it to determine whether or not to synchronize new messages.
imap.SelectFolder("Inbox");
string nextUniqueId = imap.CurrentFolder.NextUniqueId;
However, this value doesn't change when there are any other changes on the folder, such as messages being deleted. To detect this, the fastest way is to retrieve a list of unique IDs of all messages currently in the folder and check with the local database:
ImapMessageCollection messageUids = imap.GetMessageList(ImapListFields.UniqueId);
This only retrieves unique IDs of the messages and nothing more, which is usually quite fast (took about 1 second to retrieve 15000 message UIDs from our Exchange server).