Me autorespondo. Ya he solucionado el tema. No es el mejor código del mundo, pero al menos me funciona. Espero sirva a alguien, a parte de a mí, jiji
Añadí una ciudad más al código original, sólo para comprobar que funcionaba.
Código PHP:
$findme=array(
"o",
"u",
"v",
);
$data=array(
"madrid",
"barcelona",
"valencia",
"cadiz");
for($i=0 ;$i<count($data);$i++)
{
$contador=0;
for($u=0 ;$u<count($findme);$u++)
{
$found=strpos($data[$i],$findme[$u]);
if($found !==false)
{
$contador++;
}
}
if($contador===0)
{
echo $data[$i];
echo "<br>";
$contador=0;
}
}