One of our clients encountered the same behavior before few months ago and it turned out to be caused by a bug in the server. This is a sample from a communication log created using Imap object's LogWriter property:
2010-12-22 08:25:42.997 INFO Imap(1) Command: R00006 UID SEARCH UID "1064:*"
2010-12-22 08:25:43.106 INFO Imap(1) Response: * SEARCH 1063
2010-12-22 08:25:43.106 INFO Imap(1) Response: R00006 OK Search completed (0.000 secs).
Here, we asked for UIDs of messages with UID 1064 and higher. Instead, the server returned 1063, which is obviously not in this range.
This is the same behavior reported by you. It really looks like the server is always returning at minimum one message, the one with the highest UID in the mailbox. This is obviously a violation of the IMAP protocol.
For you, a simple workaround would be to to check all the returned UIDs and verify that they in fact belong to the specified range. For us, it is much more difficult because the search criteria can get complicated if one uses the Not and Or operators.