$Q_bydept = mysql_query("SELECT user.firstname, user.midname, user.lastname, department.dept_name FROM user, department WHERE user.id_dept = department.id_dept ORDER BY department.dept_name") or die (mysql_error());
	$dept_old = '';
	while ($from = mysql_fetch_array($Q_bydept))
	{
	
		if($from['dept_name']!=$dept_old) 
		{ 
			echo $from['dept_name'];
			echo '<br />';
			$dept_old = $from['dept_name']; // on met à jour le futur précédent 
		}
		
	echo '<div align="right">';
	echo $from['firstname'].'.'.$from['midname'].'.'.ereg_replace(' ', '', $from['lastname']).'@my-company.com';
	echo '<br />';
	echo 'my-company\\'.substr($from['firstname'].'.'.$from['midname'].'.'.ereg_replace(' ', '', $from['lastname']), 0, 20);
	echo '<br />';
	echo '</div>';
	}

oldLocation = ""; // on définit une variable pour stocker les locations
while(...) {
  if(...) {// on compare le location de la ligne au précédent
     // si ils sont différents, on affiche la location
     // on met à jour le location précédent
  }
  // on affiche normalement la ligne
}

Il ne te reste plus côté php, qu'à boucler normalement en stockant dans une variable temporaire le nom de la location. Ainsi, tu peux comparer le nouveau au précédent et à chaque fois qu'elle change, afficher la nouvelle

if($location!=$locationPrecedente) {
  echo $location; // affichage de la location
  $locationPrecedente = $location; // on met à jour le futur précédent
}

SELECT * FROM user WHERE location = $location['$i']