Нет, вспомогательная таблица тут не нужна.
Если нужно, чтобы между юзерами могло проходить несколько разных переписок, стоит создать таблицу Conversations (id, initiator_id, date_started, etc ... ) - не для связи, а как самостоятельную сущность, а в таблицу Messages добавить три референса - sender_id, receiver_id и conversation_id.
Но если допускается, что сообщения между двумя юзерами - всегда одна переписка, то достаточно просто в Messages добавить sender_id и receiver_id. Это однозначно свяжет каждое сообщение с двумя юзерами.
А вот если нужна переписка сразу между несколькими юзерами, тогда уже нужна вспомогательная таблица ConversationMembers (user_id, conversation_id), а из Messages нужно убрать receiver_id - сообщение и так будет связано с перепиской, и все ConversationMember'ы смогут его получить.