Mysql. Ordene ubicaciones y únase a listados al azar

Para mostrar las ubicaciones.título si la ubicación tiene al menos 1 fila asociada en la tabla de "listados", use:

SELECT loc.title
  FROM LOCATIONS loc
 WHERE EXISTS(SELECT NULL
                FROM LISTING li
               WHERE li.location = loc.id)

Usar:

  SELECT x.title, 
         x.address,
         x.distance,
         x.info,
         x.status
    FROM (SELECT loc.title, 
                 loc.address, 
                 ( 3959 * acos( cos( radians('".$center_lat."') ) * cos( radians( latitude ) ) * cos( radians( longitude ) - radians('".$center_lng."') ) + sin( radians('".$center_lat."') ) * sin( radians( latitude ) ) ) ) AS distance,
                 li.*,
                 CASE 
                   WHEN @location = loc.id THEN @rownum := @rownum + 1
                   ELSE @rownum := 1
                 END AS rank,
                 @location := loc.id
            FROM LOCATIONS loc
       LEFT JOIN LISTINGS li ON li.location = loc.id
            JOIN (SELECT @rownum := 0, @location := -1) r
        ORDER BY loc.id, RAND()) x
   WHERE x.rank = 1
ORDER BY x.distance

Con MySQL 5.1.49-community, obtuve con éxito los resultados deseados con la consulta anterior.

No puedo reproducir la fila duplicada del OP usando:

CREAR TABLAS

CREATE TABLE `locations` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` varchar(45) DEFAULT NULL,
  `address_street` varchar(45) DEFAULT NULL,
  `address_city` varchar(45) DEFAULT NULL,
  `address_state` varchar(45) DEFAULT NULL,
  `address_zip` varchar(45) DEFAULT NULL,
  `latitude` decimal(10,6) DEFAULT NULL,
  `longitude` decimal(10,6) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=latin1$$

CREATE TABLE `listings` (
  `id` int(11) NOT NULL,
  `token` varchar(4) DEFAULT NULL,
  `location` varchar(45) DEFAULT NULL,
  `info` varchar(45) DEFAULT NULL,
  `status` varchar(45) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1$$

INSERTAR declaraciones:

INSERT INTO `locations` 
VALUES (1,'John\'s Ice Cream','1701 S Martin Luther King Jr Blvd','Lansing','MI','48910','42.714672','-84.567139'),
       (2,'7 Eleven','3500 Okemos Rd','Okemos','MI','48864','42.683331','-84.431709'),
       (3,'Kurt\'s Pizza','213 Ann St.','East Lansing','MI','48823','42.736053','-84.481636'),
       (4,'Walmart','16275 National Pkwy','Lansing','MI','48906','42.780350','-84.637238'),
       (5,'Alex\'s Hot dog Shop','8505 Delta Market Dr','Lansing','MI','48917','42.739830','-84.677330');

INSERT INTO `listings` 
VALUES (19,'39c4','1','5 gallons for $8','active'),
       (21,'89dF','4','2 mens shirts for $2','active'),
       (22,'67oP','1','Ice cream cones for $1','active'),
       (23,'5tG8','2','Large soft drinks only $0.99!','active');