Now my uidnext debug traces look much better.
Thanks for the quick fix.

There was an omission - the offset needed to be reduced by the number 
of messages the client previously knew where in the mailbox.  This has 
been fixed.

Additionally, we should only be changing UIDNEXT after a mailbox is 
fully opened (i.e. after the SELECT/EXAMINE is completed).

Changes have been made in Git (master):

commit 0f4fe88f3474a442e69b25e3b99155ad1df579e2
Author: Michael M Slusarz <slusarz@horde.org>
Date:   Fri Nov 9 07:39:12 2012 -0700

     [mms] Correctly increment UIDNEXT when an EXISTS response is 
issued after the mailbox is opened (Bug #11679).

  .../Imap_Client/lib/Horde/Imap/Client/Base.php     |    1 +
  .../lib/Horde/Imap/Client/Base/Mailbox.php         |    9 ++++++++-
  .../Imap_Client/lib/Horde/Imap/Client/Socket.php   |    8 +++++---
  framework/Imap_Client/package.xml                  |    2 ++
  4 files changed, 16 insertions(+), 4 deletions(-)

http://git.horde.org/horde-git/-/commit/0f4fe88f3474a442e69b25e3b99155ad1df579e2

Hi,

the Kolab_Storage module uses a combination of uidvalidity, uidnext 
and the number of items in a folder to determine if it changed (this 
will work 99% reliable).

During my various tests I learned the hard way that uidnext is not 
what it seems to be:
An offset gets added to it. The problematic code is in 
Imap/Client/Socket.php:4117.
-------------------------------------------
     protected function 
_serverResponse(Horde_Imap_Client_Interaction_Server $ob)
     {
...
         default:
             // Next, look for responses where the keywords occur second.
             $first = $token->current();

             switch (strtoupper($token->next())) {
             case 'EXISTS':
                 // EXISTS response - RFC 3501 [7.3.2]
                 $mbox_ob = $this->_mailboxOb();
                 
$mbox_ob->setStatus(Horde_Imap_Client::STATUS_MESSAGES, $first);

                 // Increment UIDNEXT if it is set.
                 if ($uidnext = 
$mbox_ob->getStatus(Horde_Imap_Client::STATUS_UIDNEXT)) {
                     
$mbox_ob->setStatus(Horde_Imap_Client::STATUS_UIDNEXT, $uidnext + 
$first);
                 }
                 break;
-------------------------------------------

Here an offset "$first" is added to $uidnext. With my specific test, 
this turned out to be the exact next "uidnext" value so Kolab_Storage 
skipped syncing the folder even though it changed.

Why is an offset added to uidnext?
(git blame mentions some fix for "condstore + modseq").

Thomas