Que tal Paisano !
 
ummm... 
 
  
Yo lo haria de la siguiente manera ! 
1. Busco en la BD todos los usuarios como en efecto tu lo haces en el primer QUERY !  
2. Todos los resultados los intrduzco en un array. 
3. Con un For insertas los INSERT INTO  
 Código PHP:
    $sql= "SELECT NOMBRE FROM USUARIOS";
$user_sql = mysql_query($user,$conex);
$f_user = mysql_num_rows($user_sql); // Total de Filas
 
 
// relleno la Matrix con los resultados del Query($SQL)
 
for($j = 1; $j < $f_user; $j++){
    $array[$j] = mysql_result($user_sql, $j, 0);
}
//Liberas los resultados de la Memoria
mysql_free_result($user_sql);
 
// Ahora con el Array lleno con los nombres de los usuarios haces el for hasta el total de filas en el query !
 
 
for($x=1;$x < $f_user;$x++){
mysql_query(
"INSERT INTO servicio_msj (remitente, destinatario, asunto, descripcion, fecha, hora, id, prioridad)
VALUES ('$textnombre', '$array[$x]', '$asunto', '$descripcion_reportada', '$fecha', '$hora', '$id', 'a')";
} 
    
  Espero que te sirva de algo  
