Speeding up COUNT(*) - WHERE clause slowing query
Another approach to remove the OR.
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