Mysql – Optimize query or model, to get an population overview in time

I think I've got a very simple model and query, but I cannot find a way to make use of indexes to boost performance.

I wonder if there is a trick in my model, or MySQL query, to speed up the execution time to get an overview of my population at a specific time.

I have the following table which holds the status (history) of my users:

CREATE TABLE `status` (
 `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
 `user_id` varchar(9) NOT NULL,
 `status` enum('NEW','REGISTERED','CANCELED') NOT NULL,
 `timestamp` datetime NOT NULL,
 `explanation` varchar(25) NOT NULL,

 PRIMARY KEY (`id`),
 KEY `index1` (`user_id`,`timestamp`,`id`),
 KEY `index2` (`timestamp`,`user_id`,`id`),

) ENGINE=InnoDB DEFAULT CHARSET=utf8

My table will hold a lot of users (5 million), which can have one, or more statuses (so the table will probably hold 10+ million records).
Records are inserted in chronological order, so ID and timestamp are "in sync" (timestamps are not required to be unique, but the autoincrement ID's are)

What I do to get an overview of my population at a specific time is:

SELECT MAX(id) FROM `status` WHERE timestamp <= NOW() GROUP BY user_id;

Which gives me the correct ID's, but since MySQL cannot use indexes when sorting on a column (for the where clause), which is not in the GROUP BY, there is no performance.

The explain tells me:

explain SELECT MAX(id) FROM `status` WHERE timestamp <= NOW() GROUP BY user_id;
+----+-------------+--------+-------+---------------------+---------------------+---------+------+----------+-----------------------------------------------------------+
| id | select_type | table  | type  | possible_keys       | key                 | key_len | ref  | rows     | Extra                                                     |
+----+-------------+--------+-------+---------------------+---------------------+---------+------+----------+-----------------------------------------------------------+
|  1 | SIMPLE      | status | range | index2              | index2              | 8       | NULL | 13897517 | Using where; Using index; Using temporary; Using filesort |
+----+-------------+--------+-------+---------------------+---------------------+---------+------+----------+-----------------------------------------------------------+

Does anyone knows how I can optimize my model, or my query (for instance with subqueries) (, to allow MySQL to make use of indexes), and so boost performance?

What I eventually want is:

SELECT user_id, status, timestamp, explanation FROM `status` WHERE id IN (
  SELECT MAX(id) FROM `status` WHERE timestamp <= NOW() GROUP BY user_id
);