Closing for now.  Horde_Imap_Client_Ids should be rewritten at some 
point in order to better handle large ID lists, but that is a 
performance enhancement - not a bug.

Changes have been made in Git (master):

commit 03fec5f396536927a20aea9f26efc36b18c6fba3
Author: Michael M Slusarz <slusarz@horde.org>
Date:   Mon Dec 22 17:53:59 2014 -0700

     Hotfix for #13761

  .../Imap_Client/lib/Horde/Imap/Client/Base.php     |    2 +-
  1 files changed, 1 insertions(+), 1 deletions(-)

http://github.com/horde/horde/commit/03fec5f396536927a20aea9f26efc36b18c6fba3

Applying that patch seems to have made it work properly again.

Dovecot 2.2 and imapproxy make up the backend.
QRESYNC and CONDSTOR were disabled inthe capabilities sometime back 
due to problems with thunderbird but if needed I can try turning it 
back on.

Does this patch improve things for you:

diff --git a/framework/Imap_Client/lib/Horde/Imap/Client/Base.php 
b/framework/Imap_Client/lib/Horde/Imap/Client/Base.php
index 96c4fc7..087265c 100644
--- a/framework/Imap_Client/lib/Horde/Imap/Client/Base.php
+++ b/framework/Imap_Client/lib/Horde/Imap/Client/Base.php
@@ -2793,7 +2793,7 @@ implements Serializable, SplObserver
          $ids = $this->resolveIds($mailbox, $opts['ids']);

          $squery = new Horde_Imap_Client_Search_Query();
-        $squery->ids($this->getIdsOb($ids->range_string));
+        $squery->ids($ids);
          $search = $this->search($mailbox, $squery, array(
              'nocache' => true
          ));

Your backend IMAP server doesn't support QRESYNC, does it?

It seems that after the second load of this users mailbox it returns a 
single record which has a max and min which causes this spike of over 
a million array entries and reaches memory limit which was previously 
256M
Once it happens I can't use webmail for that user and I have to delete 
the users data from horde and start again, it's the same cycle.
I am unsure on how to debug this but I suspect it is to do with the 
IMAP proto returning the min and max bounds for the mailbox.

This makes no sense.  Memory is allocated per *message*.  It is 
irrelevant the gap between any two messages.

I can create an array of 10,000 IDs with a gap of 1000 between each ID 
- I see total memory usage of about 6 MB.  (100,000 IDs causes memory 
usage of ~40MB. 1,000,000 IDs causes memory usage of ~300MB).

You will need to provide a reproducible test case where 3000 IDs is 
causing memory usage of > 256 MB - I can't even get 1% of that memory 
usage.

They dont have 1M emails in the mailbox, only about 3000 but these 
users happen to have a high throughput of messages that they clear out 
each day.
The problem seems that as the user has left some messages from a few 
years back in that folder then the min/max sequence ID are very far 
apart which causes the issue.

The only way I can think to resolve the problem for him is that he 
archives the early messages away thus causing the ID range to far 
smaller.

They have 1 million messages in their mailbox?  The expectation for a 
mailbox that large MUST be that it is going to take a lot of memory.
That's exactly the issue.  You can optimize for memory, but then you 
lose speed.

Since most people have mailboxes less than 1 million messages, the 
obvious choice is to optimize this scenario.

Not to mention that there is very little you can do when working with 
a list of messages that may NOT be in sequential order.  i.e. a 1 
million element UID list where every other UID is skipped.

Doing things like binary packing and in-line compression are possible 
options, but these are complicated additions and not something that I 
am going to tackle unless someone is paying me.
This is irrelevant for PHP memory handling.  There is no direct access 
to PHP memory/garbage collection that's going to make a difference in 
this situation.

If the IMAP sequence ID between the earliest and latest messages is 
very large it is easy to hit memory limits in PHP specifically in the 
Horde/Imap/Client/Ids.php file
Why this large range happens sometimes and not always is odd and I 
have a lack of understanding on what it is doing.

Ive had an issue with one user where the range was over 1m between min 
& max and the max memory had to be over 256Mb

Using SplFixedArray the max memory limit can be reduced to about half 
but there are big issues elsewhere as the Spl does not have all the 
sort functions that a standard array has.
I am not sure if this can somehow be shoehorned in and made to work or 
if its limitations are a problem.

Another problem is found on line 170, would it not be prudant to unset 
each array key as it is populated into the _add array, that way the 
memory should not balloon (not sure if PHP optimises for this anyway).