<?php
$q = mysql_query("
 SELECT
  `city`
 FROM `orders`
 ORDER BY `id` DESC
 LIMIT 1
");
$d = mysql_fetch_assoc($q);

if(in_array($d['city'], $city_array)) {
 // Город есть в последней записи таблицы orders
} else {
 // Запрос на добавление города
}
?>