Allora..
Il database è il utf8_general_ci, inserendo il $mysqli->set_charset("utf8_general_ci"); vengono visualizzate correttamente le lettere stampate con PHP, tuttavia l'str_replace continua a non trovare le lettere accentate..
Un'altra cosa che potrebbe essere importante è che se inserisco il <meta charset="UTF-8"> le lettere accentate vengono nuovamente sostituite dal rombo con il punto interrogativo..!
--edit--
Risoltooooo!!
Grazie
Ho messo utf8 al posto di utf8_general_ci