Y bueno tendrás que hacer varios inserts en tu tabla, no tenes otra, por un lado recaudar todos los usuarios del sistema menos el que envía, esto te quedará en 1 array, y por otro lado vas haciendo con 1 bucle varios inserts tomando de a 1 los usuarios que quedaron de tu consulta anterior en el array y enviarles el mensaje.
Código SQL:
Ver originalinicio bucle()
INSERT INTO tabla ID_mensaje, fecha, de, para_usuario1, asunto, mensaje, leido´
}fin bucle
donde para_usuario1 sera un valor que valla tomando del array en donde te quedaron los usuarios que recuperaste con tu consulta.
Creo que podría ser así.