The optimization process and recommendations:

1. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.
2. Mixed Order By Directions Prevents Index Use (query line: 15): The database will not use a sorting index (if exists) in cases where the query mixes ASC (the default if not specified) and DESC order. To avoid filesort, you may consider using the same order type for all columns. Another option that will allow you to switch one direction to another is to create a new reversed "sort" column (max_sort - sort) and index it instead.
3. Use Numeric Column Types For Numeric Values (query line: 12): Referencing a numeric value (e.g. 90808) as a string in a WHERE clause might result in poor performance. Possible impacts of storing numbers as varchars: more space will be used, you won't be able to perform arithmetic operations, the data won't be self-validated, aggregation functions like SUM won't work, the output may sort incorrectly and more. If the column is numeric, remove the quotes from the constant value, to make sure a numeric comparison is done.

Optimal indexes for this query:

ALTER TABLE `ESB_MSG_L` ADD INDEX `esb_l_idx_msg_id_msg_ts` (`MSG_ID`,`Msg_Ts`);
ALTER TABLE `ESB_PAYLOAD_L` ADD INDEX `esb_l_idx_msg_id` (`MSG_ID`);

The optimized query:

SELECT
        M.MSG_DESC,
        M.Msg_Ts 
    FROM
        INTLOG.ESB_MSG_L M,
        INTLOG.ESB_PAYLOAD_L P 
    WHERE
        M.MSG_ID = P.MSG_ID 
        AND M.Msg_Ts >= TIMESTAMP '2014-02-16 00:00:00' 
        AND M.Msg_Ts <= TIMESTAMP '2014-02-17 12:00:00' 
        AND M.Msg_ID IN (
            '90808', '67678', '534534'
        ) 
    ORDER BY
        M.MSG_TS,
        p.payload_corl_id DESC