Holas, franjgg.
 
Sólo debes modificar levemente tu código para que funcione como quieres:  
 Código PHP:
    while ($ultimo_fila = mysql_fetch_array($resultado_fila)){
    if($ultimo_fila['id_direccion'] != $comprobacion){
    $consulta_localidad = "select p.id, p.descripcion, m.id, id_provincias, m.descripcion as localidad FROM provincias p Inner join municipios m On p.id = m.id_provincias where m.id = ".$ultimo_fila['id_municipios'];
    
    $resultado_localidad = mysql_query($consulta_localidad);  
    $ultimo_localidad = mysql_fetch_array($resultado_localidad);
    
        echo '<div style=" border-bottom:solid 1px #0094d6; border-top:solid 1px #a6d3e7; padding:20px 20px 20px 30px; background: -webkit-linear-gradient(#FFFFFF, #EFEFEF); background: -moz-linear-gradient(#FFFFFF, #EFEFEF); background: -o-linear-gradient(#FFFFFF, #EFEFEF); background: linear-gradient(#FFFFFF, #EFEFEF); ">';
        echo '<img src="logo_negocios/'.$ultimo_fila['id'].'/'.$ultimo_fila['logo'].'" style="max-width:150px;">';
        echo '<p style="font-size:14pt; line-height:10px; color:#00aef4;">'.utf8_encode($ultimo_fila['nombre_direccion']).'</p><span style="font-size:8pt; line-height:17pt; color:#000000;">'.utf8_encode($ultimo_fila['direccion']).'<br>'.$ultimo_fila['cp'].' '.utf8_encode($ultimo_localidad['localidad']).' - '.$ultimo_fila['telefono'].'<br></span>'.$ultimo_fila['email_direccion'].' - '.$ultimo_fila['web'];
        echo '</div>';
      }
    // esto debe ir fuera del IF, ya que siempre tiene que guardar el último ID
    $comprobacion = $ultimo_fila['id_direccion'];
    } 
    
  Saludos!