Se imposti correttamente il charset del file php e lo specifichi anche nel tag meta, non tiserve nessun str_replace, utf8 gestisce correttamente le lettere accentate.

Comunque non è chiaro da dove ti arrivino le lettere accentate, da un db o da un form?