Very common mysql query sometimes does not use index
While I am unable to explain why MySQL occasionally decided not to use index on a very obvious and very common query, the solution was to simply force the index.

In my particular case:

select msg_cont, msg_u_code, msg_d_t, msg_viewed, usr_u_code, usr_name from
        (select
            msgs.id as msg_id,
            msgs.cont as msg_cont,
            msgs.u_code as msg_u_code,
            msgs.d_t as msg_d_t,
            msgs.viewed as msg_viewed,
            usrs.u_code as usr_u_code,
            usrs.usr_name as usr_name
            from msgs FORCE INDEX (convo)
            left join usrs FORCE INDEX (u_code) on msgs.sender = usrs.u_code
    where  msgs.convo = 'aaaaaaaaaabfbaghdgcigfid_aaaaaaaaaabeiaccjfhjfach'
      and  (msgs.sender = 'aaaaaaaaaabfbaghdgcigfid'
              or  msgs.receiver = 'aaaaaaaaaabfbaghdgcigfid'
           )
      and  msgs.stat = '1'
      and  usrs.stat = '1'
      and  usrs.u_code not in('aaaaaaaaaabfaagfbgggiejh',
                              'aaaaaaaaaabfabgbjdfjigbd',
                ...... !!!!![here go 400 more usr_u_codes]!!!!!
                          )
      and  msgs.id &gt; 30997997
        ) a order by msg_id asc;


Slow query log proved this solution to be effective as no new slow entries emerge.