Por fin lo solucioné! A parte de tener todo en UTF8 y demás usé esta sentencia que "fuerza" a la base de datos a usar utf8:
Código MySQL:
Ver original$conectaI = ...... conexión que tengamos.
mysqli_query($conectaI,"SET character_set_results = 'utf8', character_set_client = 'utf8', character_set_connection = 'utf8', character_set_database = 'utf8', character_set_server = 'utf8'");
Ahora me guarda en cualquier idioma correctamente. Y por supuesto ya los utf8_encode y utf8_decode ya sobran. Jeje, menos mal!
Un saludo.