Scusa, ma da qualche parte avrai la stampa del messaggio, no? li devi usare urldecode.
Dovresti avere qualcosa del genere:
Codice PHP:
if($citta === " ")
    {
        
$messaggio urlencode("Non hai inserito la città");
        
header('location: '.$_SERVER['PHP_SELF'].'?msg='.$messaggio);
        exit();
    }
...
if(isset(
$_GET['msg'])){
   echo 
urldecode($_GET['msg']);