There doesn't need to be a temporal paradox to explain the seeming inconsistency about Borg knowledge prior to "Q Who." As Poul Anderson pointed out in his Polesotechnic League/Terran Empire series, a multiplanet interstellar community is so vast that there's no way any one person could be aware of all the available information about it. You may be informed and well-traveled and cosmopolitan, but there will still be planets within your own civilization that you've never even heard of. And when you're dealing with the knowledge of other, neighboring civilizations throughout the galaxy as well, there are bound to be even more things that a given individual has never heard of. (Remember how in "The Last Outpost," Picard had never heard of the Tkon Empire, even though he was later established as an expert in archaeology? While that was a continuity error, it's one that can easily be explained without resorting to history being changed. It's logical to conclude that there are so many ancient civilizations in the galaxy that Picard couldn't possibly know about every one that the Federation has ever discovered.)
True, the Borg thing is a bit more of a glitch, since the ship's computer in "Q Who" didn't seem to have any record of them. But I resist crying "history was changed!" every time there's a minor continuity hiccup in Trek, because there are hundreds of them and so that would get ridiculous. And I prefer to think that the body of aired canon represents a largely consistent timeline rather than several different ones. The intent of ENT's producers was that their show represented the events that led into TOS itself, not a separate timeline branching away from it. And that's my assumption as well.
Besides, we know from "Q Who" itself, as well as Generations, that Guinan and her people knew about the Borg and that they came to the Federation decades earlier. So it stands to reason that the El-Aurian refugees would've mentioned the Borg to someone. Even without the later temporal hijinks, it's illogical to assume the Borg were completely unknown when the very episode that introduced them tells us outright that one of the show's major characters has known about them all along.
So my take, which I actually did spell out in Watching the Clock, is that the Borg had been heard of prior to "Q Who," but only as a vague galactic legend that wasn't widely known beyond certain fringe regions of Federation space. Magnus Hansen's research of that legend was known to the Federation's scientific establishment, but probably not taken seriously, or given much attention relative to the vast amounts of other research that establishment must've been involved with. It's a big galaxy.