No se que tipo de mansaje querés, pero lo que si se es donde habría que ponerlo
Código PHP:
if (mysql_num_rows($resultado)>0)
{
if(ENVIAR MENSAJE){//ACA ES DONDE HAY QUE PONERLO, JUSTO ANTES DEL DELETE
$sql="delete from t_usu where clave=$elimina";
mysql_query($sql,$conexion) or die ("Se creo un error al tratar de dar de baja al usuario");
header("location:bajacorrecta.php");
}
}