Para verificar que el archivo no existe ya, podes usar la funcion file_exists()
http://ar2.php.net/file_exists
Y para generar ese formato de nombre de archivo, podes hacer algo como lo siguiente:
Código PHP:
$random = rand(0, 999999);
$fecha = date("d-m-Y", time());
$nombre_archivo = $fecha . '_' . $random . '.msg';
Luego compruebas si el archivo existe con la funcion file_exists(), y lo creas si no existe, caso contrario vuelves a crear un nombre de archivo.