There is no way to track the number of changes made by Find & Replace.
If you wanted to have the Time Stamp update only for records that changed, you would need to first select records that contain what you want changed, and then do the Find & Replace.
I do not consider the way it works currently to be a bug. I suppose it could be a feature request. If this change were made, it should probably be more general. For example, if you used FormulaFill to fill a field with zero, but many records already contained zero, this question would also apply.
Note: I moved this topic from the SetChanges thread, since it really was not connected to that discussion. In older versions that did use SetChanges, the Find & Replace operation would always indicate that one change had been made to the database, no matter how many records had actually changed (or even if no records had changed).