Mensajeria en PHP

[morfasto]

Hola, que tal?

Estoy haciendo un sistema de mensajes en mi pagina web para que los usuarios puedan comunicarse entre ellos.

Esta es la estructura de las tablas que he decidido hacerle para que funcione bien:

Mensajes:
mensaje_id
fecha_envio
titulo
contenido
estado ('leido', 'sin_leer') DEFAULT 'sin_leer'

Mensajes_Relaciones:
mensajes_relaciones_id
mensaje_id
de_usuario_id
para_usuario_id

El problema esta a la hora de insertar un registro a las tablas, ya que la tabla Mensajes_Relaciones requiere de mensajes.mensaje_id para poder llenar su campo mensajes_relaciones.mensaje_id.

Alguna idea de como puedo hacer esto?

Muchas gracias por su cooperacion!