I can only confirm that I've seen/had a very similar problem, but (1) refixing did solve it, (2) there was a perfectly reasonable cause for it (using too dilute fixer one shot; I was seeing how little I could get away with) and (3) it didn't involve sprocket hole anomalies, but rather followed different patterns.
Sprocket-hole related anomalies are a bit more likely to point towards light leak problems during film handling, esp. if they're along one edge.
The stain is also strongest ALWAYS on the same side of the negatives regardless of their location in the tank (more towards the bottom or top).
That's an important clue and it points more towards a light leak issue than one with chemistry.
In what part of your total film handling process do the films have the same orientation?
Can you confirm it's always the bottom edge of the film that's affected?
How do you handle the exposed film; i.e. what's your process of getting it from its packaging into the processing tank?
What kind of tank do you use? (5-reel Paterson; you mentioned it)
You mention it also occurs on 120 film; what does it look like in that case?
Can you show examples scanned edge to edge and not just the image frame? Does the problem show on non-image areas (film edges, leader/trailer sections)?