Probably better at reporting this here:

https://github.com/jonabbey/panda-imap

True, the ranges in ESEARCH UID response are broken (non UID responses 
are not affected).  It is IMAP-UW, not Horde's bug.

As IMAP-UW is no longer developped, I attached the patch for IMAP-UW 
here - it may help to someone using Horde against IMAP-UW server.

Ok, disregard my previous question then - that explanation does make sense.

You can close this ticket then.  I'll keep an eye to see if the issue 
appears in other malboxes, in which case I will disable the ESEARCH 
extension.

Thanks!

Why would the issue disappear then when switching to an older version 
of IMP?  More robust handling perhaps?

If that's the case, then the local cached information on your IMAP 
server is broken.  This is not an IMP issue.

Something seems badly broken on your IMAP server.

IMP correctly asks for the list of messages in the mailbox:

(1307732082,2502) C: 4 UID SEARCH RETURN (ALL COUNT) ALL

However, the IMAP server reports that ALL UIDs between 316 and 615 exist:

(1307732082,2506) S: * ESEARCH (TAG "4") UID ALL 316:615 COUNT 131

However, that can't be right since it also reports that there are only 
131 messages in the mailbox, but the UID response indicates that there 
is 300 messages.  So the ESEARCH response is broken.

You wouldn't see this on other IMAP clients (e.g. IMP 4) because many 
of them don't support the new ESEARCH return.  You could work around 
this by disabling the ESEARCH extension in imp's backends.php file, at 
the expense of less efficient SEARCH queries (assuming that regular 
SEARCH queries are not broken).

Additional information: while trying to generate a smaller testcase 
mbox, I discovered that the problem disappears if I delete the UW-IMAP 
internal folder data message from that mailbox.  I'm attaching it here 
in case it could be of help.

I still got a backup of the whole mailbox in case you need it (but I 
would like a more secure way to send it to you than a public ticket 
tracker).  It's a 23M gzipped file.

Here's is the debug_raw output.  Steps done:

- Logged in
- Went to Inbox
- Logged off.

To further debug this issue, we need details of the IMP -> IMAP/POP 
communication.

To enable debugging, see instructions contained in 
imp/config/backends.php (the 'debug' config parameter).

Debugging should not be enabled on a production server,   Attach/post 
only the portion of the log that directly deals with the problem 
reported (it may be simplest to clear the log file and then perform 
the event that causes the error).

Since upgrading from IMP 4 to 5, IMP fails at properly displaying a 
list of messages for some of my users.  It will list one or two emails 
in the page, one of them saying Unknown date, Invalid Address, etc...   
DIMP will fail to build a list, simply saying there was an error.

Switching back to IMP 4.x works fine with the same mailbox, so this 
looks like a regression.

The Horde logged message:
2011-06-10T12:23:09-04:00 WARN: HORDE [imp] PHP ERROR: array_flip() 
[<a href='function.array-flip'>function.array-flip</a>]: Can onl
y flip STRING and INTEGER values! [pid 3184 on line 64 of 
"/usr/share/pear/Horde/Imap/Client/Utils.php"]

Note that some Emails might have French accents in their subject or 
body, in case that'd be the trigger.