As a side note, I found on the web (http://word.mvps.org/faqs/MacrosVBA/...placements.htm) a method that can be used to keep track of the number of replacements done through the function Replace(), so this part is not an issue anymore.
Now, I still have the same concern regarding processing speed in big documents, as all headers are checked without consideration to their state. If anyone can help on this part, it would be great...
Using the algorithm fumei wrote, I assume there must be a way to add a few lines to check if ".LinkToPrevious = False" in the different headers? I'm not quite sure how to write this, as there are 3 possible headers in a Word file...