Changes have been made in Git (master):

commit 36e89195bff18e7273e891f58867291f7ed68ad6
Author: Michael J Rubinsky <mrubinsk@horde.org>
Date:   Tue Jul 23 23:54:48 2013 -0400

     Bug: 12476  ORDER BY/LIMIT gives greater performance boost.

  framework/History/lib/Horde/History/Sql.php |    4 +++-
  1 files changed, 3 insertions(+), 1 deletions(-)

http://git.horde.org/horde-git/-/commit/36e89195bff18e7273e891f58867291f7ed68ad6

I think what's happening with the MAX query is that the index is in 
ASC order and the order of the columns in the composite index is in 
the wrong order. Creating the composite index on object_uid, 
history_modseq (instead of history_modseq, object_uid) reduces the 
number of rows to scan for me by multiple orders of magnitude.

ORDER BY/LIMIT query also seems to greatly improve performance as 
shown by EXPLAIN on my production server.  My development server uses 
the less efficient filesort but I'm thinking that's because the number 
of rows is much smaller.

Hah. Of course, the exact opposite of what I thought :)

Add. Note: After applying the patch the load on the database server 
went from 15-20 down to 0.xx

This is the patch:

--- /usr/share/php/Horde/History/Sql.php        2013-07-15 
03:06:20.976871299 +0200
+++ /xxx/Horde/History/Sql.php  2013-07-22 11:23:27.641122721 +0200
@@ -293,10 +293,11 @@
       */
      public function getHighestModSeq($parent = null)
      {
-        $sql = 'SELECT MAX(history_modseq) FROM horde_histories';
+        $sql = 'SELECT history_modseq FROM horde_histories';
          if (!empty($parent)) {
              $sql .= ' WHERE object_uid LIKE ' . 
$this->_db->quote($parent . ':%');
          }
+        $sql .= ' ORDER BY history_modseq DESC LIMIT 1';

          try {
              $modseq = $this->_db->selectValue($sql);

Thanks for the feedback - here is what I found out. I suggest to 
reopen the ticket. (see below)
It's now using the index - but the query itself becomes even slower:

Before:

1.13 sec

After:

2.30 sec

(Indeed EXPLAIN shows that the index history_modseq is used)
0.00 sec (!!!)

So this solves the speed issue.
It think it's worth a test because the performance raise in MySQL is 
DRAMATICALLY. The key length (according MySQL explain) that is used is 
now 4 instead of 767. Maybe this could be the reason for the gain.

commit 96efec1aaa1a54b2f7a7f5251fad4a295dbb0910
Author: Michael J Rubinsky <mrubinsk at horde.org>
Date:   Sun Jul 21 14:13:05 2013 -0400

     Add composite index for modseq queries.

  .../Horde/History/4_horde_history_add_compositeindex.php          |   
  15 +++++
  1 files changed, 15 insertions(+), 0 deletions(-)
  create mode 100644 
framework/History/migration/Horde/History/4_horde_history_add_compositeindex.php

http://git.horde.org/horde-git/-/commit/96efec1aaa1a54b2f7a7f5251fad4a295dbb0910

Since my history data set, even on production is not anywhere near as 
large as your data set, can you see if adding the following index 
improves this for you? EXPLAIN now shows that it is using the index so 
it should improve...

ALTER TABLE horde_histories ADD INDEX (history_modseq, object_uid);


If not, the next attempt would be to use something like:

  SELECT history_modseq FROM horde_histories WHERE object_uid LIKE 
'turba:%' ORDER BY history_modseq DESC LIMIT 1;

but I'd be wary of doing this since I doubt it would perform the same 
from one RDBMS to another.

After updating to v 5.1.1 the database causes huge load while running 
queries of these type:

SELECT MAX(history_modseq) FROM horde_histories WHERE object_uid LIKE 
'turba:%';

mysql> EXPLAIN SELECT MAX(history_modseq) FROM horde_histories WHERE 
object_uid LIKE 'turba:%';
+----+-------------+-----------------+-------+-----------------+-----------------+---------+------+--------+-------------+
| id | select_type | table           | type  | possible_keys   | key   
           | key_len | ref  | rows   | Extra       |
+----+-------------+-----------------+-------+-----------------+-----------------+---------+------+--------+-------------+
|  1 | SIMPLE      | horde_histories | range | history_uid_idx | 
history_uid_idx | 767     | NULL | 999027 | Using where |
+----+-------------+-----------------+-------+-----------------+-----------------+---------+------+--------+-------------+
1 row in set (0.00 sec)

The system becomes nearly unusable because of these queries.