Llevo ya bastante rato probando de todo, y tengo todos los archivos guardados en UTF-8 sin BOM, todas las bases de datos y tablas en UTF8, los meta tambien.
Me he dado cuenta que si guardo en la base de datos cualquier caracter extraño desde el formulario de envio, luego al mostrar los elementos que hay lo saca correctamente. Pero eso no pasa con las provincias.