A ver, mas o menos he visto casi todos los mensajes.
El tema es que se están dando indicaciones para verlos correctamente al recoger los datos de la consulta. Pero tu necesitas hacerlo antes de consultar, para que al comparar, el resultado sea idéntico.
Código PHP:
$ciudad=utf8_decode($_POST['ciudad']);
$query="SELECT cliente.nombre, contacto.ciudad,
FROM cliente,contacto
WHERE contacto.ciudad='$ciudad'
AND cliente.contacto_idcontacto=contacto.idcontacto
ORDER BY DESC();
Y después para mostrarlos si utilizas utf8_encode() como se ha indicado.
Si no me he perdido mucho al leer creo que es esto el problema.
Prueba y nos cuentas.
PD.: SI te sigue dando error, muéstranos, por una lado el code de la consulta, y por otro el code para mostrar los resultados.