Keep in mind that there was a Borg cube skulking around the Neutral Zone in late TNG Season 1.
Quite so. The idea that the ship in "BoBW" would have reached the Federation at impossibly high speeds comes from Data's assertion that the dimensions of the ship in the episode are exactly the same as those of the ship previously encountered in "Q Who?", approximately 7,000 ly away from the Federation. And Data might have been wrong.
Or, more probably, Borg Cubes come in standard sizes even if individual ships can be identified by their details. And the details might change with time, as the ships repair themselves or improve themselves. So the ship that scooped up the Jouret colony may not have been the one that offed J-25 previously. And it may or may not be the same that destroyed the RNZ outposts.