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_type_idmessage_id
FROM messages
WHERE message_type_id = 1 AND hidden = 0
UNION
SELECT message_type_idmessage_id
FROM messages
WHERE message_type_id = 1 AND message_id = @message_id
) X