Query not using index sporadically

[Vinay NP]

We have a query which runs on a table with ~50M rows. The query does not use the correct index sometimes. This happens only once in a while and we have so far been unsuccessful in finding a pattern. Whenever this does happen, more queries start piling up and the entire db becomes sluggish.

I've illustrated the query and the table structure (similar to original) below.

Table 1 (~50M rows) Structure
-----------------
CREATE TABLE IF NOT EXISTS `rluf` (
`id` int(11) NOT NULL,
`group_id` varchar(13) NOT NULL,
`email` varchar(100) NOT NULL,
`mobile` varchar(50) NOT NULL,
`name` varchar(200) NOT NULL,
PRIMARY KEY (`id`),
KEY `group_id` (`group_id`),
KEY `email` (`email`),
KEY `mobile` (`mobile`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

Table 2 Structure
-----------------
CREATE TABLE IF NOT EXISTS `rlbl` (
`id` int(11) NOT NULL,
`group_id` varchar(13) NOT NULL,
`user_id` varchar(100) NOT NULL,
`status` varchar(100) NOT NULL,
`type` varchar(50) NOT NULL
PRIMARY KEY (`id`),
KEY `group_id` (`group_id`),
KEY `user_id` (`user_id`),
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

Query
-----
SELECT DISTINCT
rlbl.group_id,
rlbl.status,
rluf.email,
rluf.mobile,
rluf.name,
rlbl.type
FROM
`rlbl`
RIGHT JOIN
`rluf` ON ( rlbl.group_id = rluf.group_id )
WHERE
`rlbl`.`user_id` IN (
'kjsdhjs5354bkdf',
'kjbsdkbsd232323'
)
;

This query works fine when it uses the intended indexes rlbl.user_id and rluf.group_id. However, at times it does not use rluf.group_id and then the problem described above happens.

Some observations
1. Checked query plan for key usage other times -- indexes are used as intended
2. Checked query plan for key usage during issue -- indexes are not used as intended. rluf.group_id index not used resulting in full table scan.
2. Checked any deadlocks during failure -- No deadlocks
3. Forced index -- Not effective

MySQL version: 5.1.52-log

Any help regarding why this issue might be occuring and what could be the possible resolution is appreciated.