I think I've found the source of a bug which I first saw when running dovecot and pine (or alpine), which I finally tracked down by doing a protocol trace. In the IMAP session, the SEARCH command appears to have a problem with sets of messages and/or the NOT operator.
Probably the best way to show this is by doing operations on a folder with ten messages in it.
a select ten
FLAGS (\Answered \Flagged \Deleted \Seen \Draft)
OK [PERMANENTFLAGS (\Answered \Flagged \Deleted \Seen \Draft \*)] Flags permitted.
10 EXISTS
0 RECENT
OK [UNSEEN 1] First unseen.
OK [UIDVALIDITY 1190450101] UIDs valid
OK [UIDNEXT 11] Predicted next UID a OK [READ-WRITE] Select completed.
Now, start doing some basic searches using message sets:
b search (1:10)
SEARCH 1 2 3 4 5 6 7 8 9 10 b OK Search completed.
OK, so far so good. Try the inverse:
c search not (1:10)
SEARCH c OK Search completed.
OK.
d search not (1,10)
SEARCH d OK Search completed.
Hmm, should have output 2..9.
e search not (2,10)
SEARCH 1 e OK Search completed.
Hmm.. that should have been 1, 3..9.
f search not (2:10)
SEARCH 1 f OK Search completed.
OK, expected.
g search not (1,9)
SEARCH 10 g OK Search completed.
Seems to affect other end of the range as well.
h search not (2,9)
SEARCH 1 3 4 5 6 7 8 10 h OK Search completed.
OK working again.