Lo que sucede es que al aplicar el primer cambio Camagüey con enlace, se cambio todas esas palabras en el texto, es decir "ciudad de <a>Camagüey</a> " me entiendes , y tu quieres reemplazar ciudad de Camagüey y esa palabra ya no esta ( ya que la reeplazaste antes por los <a> y la palabra).
Lo que puedes hacer es ir aplicando str_replace primero a las subcadenas mas larga hasta las mas pequeña
Que tu array sea ordenado asi
Código PHP:
$indices = array("provincia de Camagüey","ciudad de Camagüey","Camagüey");
Saludos