Yikes you need to understand headers and sections! But first:

I still have the same concern regarding processing speed in big documents, as all headers are checked without consideration to their state.
Perhaps, but checking their state also takes processing. I am not sure how much a InStr test takes more than a If LinkToPrevious = False test.
- using the whole header range is very interesting, but replacing it actually overwrites the whole header, including any text box.
First of you never mentioned any text box. Second my good (sans any textbox) does not replace the whole header, only the "old stuff" string. Everything else remains.

I remain a bit off put by what SEEMS to be happening. Let me see if I have this.

You have users that will VERY OFTEN need to change existing headers. I say very often because if it is NOT often, then are you concerned about performance times. if it is a uncommon event, hey start it and go to lunch. Big deal.

The user will use RANDOM strings of text.
I don't actually know what they are, since they can be different every time.
So...there is no logic behind what the string will be. Right?

If any given section header is linked to the previous (same) header type in the previous section it is assumed that that header is correct and NO test of the current header content needs to be done. Really? Not sure why I am sceptical about that, but what do I know? BTW "for in the parent sections" - there is no such thing as "parent" sections

Somehow the user can get a search string into the procedure (although how is not stated...inputbox, the user selects some text in the document and THAT is used???), and in some manner "tags" are added to that string.
Consider the fact that if a 500 pages document has 100 different sections (i.e. say 100 different headers and 400 "linked headers"),
Umm, that is not a fact. First, the number of pages is completely irrelevant. You seem to think there is a header for each page. Not so. The number of pages has nothing to do with sections. Nothing. You can have a 1000 page document with ONE section, in which case the code will run pretty darn fast. Secondly a document with 100 sections will have 300 headers whether they are linked, or not. LinkToPrevious has NOTHING to do with the number of headers. Or the number of pages.

Anyway, you seem to be moved along fairly well. I am not sure I can help much more.