Optimize query or model, to get an population overview in time
Ok, i tried to reproduse your case:

mysql&gt; insert into status values (1,'a','NEW',NOW(),'test'); Query OK, 1 row affected (0.00 sec)

mysql&gt; insert into status values (2,'b','NEW',NOW(),'test2'); Query OK, 1 row affected (0.00 sec)

mysql&gt; insert into status values (3,'c','NEW',NOW(),'test3'); Query OK, 1 row affected (0.00 sec)

mysql&gt; explain  SELECT MAX(id) FROM `status` WHERE timestamp &lt;= NOW() GROUP BY user_id;
+----+-------------+--------+-------+---------------+--------+---------+------+------+--------------------------+
| id | select_type | table  | type  | possible_keys | key    | key_len | ref  | rows | Extra                    |
+----+-------------+--------+-------+---------------+--------+---------+------+------+--------------------------+
|  1 | SIMPLE      | status | index | index2        | index1 | 41      | NULL |    3 | Using where; Using index |
+----+-------------+--------+-------+---------------+--------+---------+------+------+--------------------------+


Mysql uses index like you wanted.

And then:

mysql&gt; alter table status drop index index1;
Query OK, 0 rows affected (0.00 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql&gt; explain  SELECT MAX(id) FROM `status` WHERE timestamp &lt;= NOW() GROUP BY user_id;
+----+-------------+--------+-------+---------------+--------+---------+------+------+-----------------------------------------------------------+
| id | select_type | table  | type  | possible_keys | key    | key_len | ref  | rows | Extra                                                     |
+----+-------------+--------+-------+---------------+--------+---------+------+------+-----------------------------------------------------------+
|  1 | SIMPLE      | status | index | index2        | index2 | 41      | NULL |    3 | Using where; Using index; Using temporary; Using filesort |
+----+-------------+--------+-------+---------------+--------+---------+------+------+-----------------------------------------------------------+
1 row in set (0.00 sec)


The plan is like yours. Please ensure that index1 is really present.

I am runnig mysql 5.5.33-31.1-log
You can even try 5.6.

Also please try to force index1 and post the results.