In the episode "Gift" (the one where Kes leaves), Seven describes to Harry Kim a cluster of galaxies where the Borg assimilated some species.
Harry Kim: "You said the Borg got this stuff from Species 259. Who were they? ... I guess the Borg meet a lot of people, don't they? Stupid question... So what's it like out there in galactic cluster three?"
Seven of Nine: "Beyond your comprehension."
HK: "Try me."
Seven of Nine: "Galactic cluster three is a trans-material energy plane intersecting 22 billion omni-cordial lifeforms."
HK: "Oh. Interesting."
So, I would be inclined to believe that yes the Borg have traveled outside the Milky Way. Especially if they happened to assimilate immigrant ships/lifeforms from other galaxies that have made their way to the Milky Way (such as the Gekli).
There's no reason to believe that the Galactic Barrier would be a problem for trans-warp capable species. There's also no reason to believe that an entity like the Borg, with a nasty thirst for knowledge, wouldn't send scout ships to do recon in other galaxies ahead of invasion forces, then re-merge with the rest of the collective when they get their subspace amplifiers and trans-warp hubs in place.