Estoy usando SQL Server 2008, no dices qué base de datos estás usando.
A partir de la información que ha proporcionado, su consulta parece demasiado compleja para el resultado que necesita. Aquí hay una consulta simple para obtener todos los mensajes relacionados con el usuario 36:
SELECT
sender.msg_user_name AS sender_user_name
,recipient.msg_user_name AS recipient_user_name
,msg_date
,msg_text
FROM
dbo.Fed_Messages
INNER JOIN dbo.Fed_User AS sender
ON sender.msg_user_id = sender_user_id
INNER JOIN dbo.Fed_User AS recipient
ON recipient.msg_user_id = recipient_user_id
WHERE
sender_user_id = 36
OR recipient_user_id = 36
ORDER BY
msg_date DESC
Tuve que cambiar algunos nombres de campo ya que en SQL Server algunos de los nombres que ha elegido son palabras reservadas.
SQL Fiddle:http://sqlfiddle.com/#!3/b8e88/1
EDITAR: Ahora ha agregado más información y se muestra que hay un id en la tabla de mensajes, podría usar algo como esto (nota:tengo SQL Server, por lo que probablemente tendrá que cambiar la consulta de MySQL):
SELECT sender.msg_user_name AS sender_user_name
,recipient.msg_user_name AS recipient_user_name
,msg_date
,msg_text
FROM dbo.Fed_Messages
INNER JOIN dbo.Fed_User AS sender ON sender.msg_user_id = sender_user_id
INNER JOIN dbo.Fed_User AS recipient ON recipient.msg_user_id = recipient_user_id
INNER JOIN ( SELECT MAX(id) AS most_recent_message_id
FROM dbo.Fed_Messages
GROUP BY CASE WHEN sender_user_id > recipient_user_id
THEN recipient_user_id
ELSE sender_user_id
END -- low_id
,CASE WHEN sender_user_id < recipient_user_id
THEN recipient_user_id
ELSE sender_user_id
END -- high_id
) T ON T.most_recent_message_id = dbo.Fed_Messages.id
WHERE sender_user_id = 36
OR recipient_user_id = 36
ORDER BY msg_date DESC
El SELECT en el FROM parte de la consulta encuentra el mensaje más reciente (basado en el id , supongo que es un número de incremento automático) para cada par ordenado de ID de usuario de remitente/destinatario. El resultado de eso se vuelve a unir a los Fed_Messages tabla para asegurarnos de obtener los nombres correctos para el remitente/receptor.
SQL Fiddle actualizado:http://sqlfiddle.com/#!3/1f07a/2
