Another approach to remove the OR.<br>
You could try this and have 2 indexes on the table to satisfy the WHERE clauses.

    SELECT
        COUNT(*)
    FROM
        (
        SELECT message_id
        FROM messages
        WHERE message_type_id = 1 AND hidden = 0
        UNION
        SELECT message_id
        FROM messages
        WHERE message_type_id = 1 AND message_id = @message_id
        ) X