Stored procedure optimization
Your use of this term

(Coalesce(xmd.Message_Status, 'Sent') = @Status OR @Status = '') 


in your inner WHERE clauses is non SARG-able, so no index can be used. Change both occurrences as shown below, to make this term SARG-able:

(xmd.Message_Status  = @Status 
    OR (xmd.Message_Status is NULL AND @Status = 'Sent')
    OR @Status = '')