I have a new template that we need to apply to 100s of legacy documents. The style names are the same in the template and the files (they are primarily built-in Heading styles).

Users are reporting that, in some files, when attaching and updating the template, the white space between two styles is added together, but not completely, instead of blended.

In other words, Heading 1 has 12 points of white space after, and Heading 2 has 12 points before. When an H1 and H2 paragraph are adjacent, instead of getting a total of 12 points of space between the two, we're getting about 20 points.

I suspect that this may be due to content that was upsaved from a .doc file at some point, but I don't know.

Any ideas on why this is happening and how to deal with it?

It could be different versions of Word.
It could be different settings on the individual computer, especially in compatibility options. Take a look at this one:

Unticking Don't use HTML paragraph auto spacing fixed it -- thank you, Charles!