- использовать параметр $count в свежем PHP 5.1+
- сравнить длины строк
- сравнить содержимое строк
- предварительно вызвать preg_match и запомнить, было ли совпадение
- установить некий (о ужас, глобальный) флаг в callback-функции, вызываемой по preg_replace_callback
- попытаться извратиться и передать в preg_replace_callback замыкание, которое будет хранить в себе количество замен