DS9's The Search occurred on stardate 48213..1. Caretaker took place in 48315.8. The first encounter with the Jem'Hadar would have been a while before The Search since it took a while for Sisko to go back to Earth and get the Defiant before we first see it in The Search. That means at least couple months would have passed between the destruction of the Odyssey and Voyager getting lost. More than enough time for Janeway and certain officers to know of them, all that.
assuming of course the reason for the Odysseys destruction wasn’t covered up. Starfleet could have easily said it was destroyed by some kind of stellar phenomenon. where my hang up is with First Contact. Seven knew the Borg were there and that happens to not too long before the war starts. One could assume Starfleet Captains/Admirals know about the Founders and surely some down the line officers do too. I can’t imagine a Starfleet officer that had that kind of info wasnt assimilated before she left. not to mention the Changeling scare on Earth in Homefront/Paradise Lost. but it does get a bit nitpicky the further down the rabbit hole you go with it.
That's what I said At the very least, VOY's database should have had data that the Dominion (more specifically, the Jem'Hadaar) destroyed the Odyssey. However, we don't know if the events in 'The Search' (aka, reports from the Defiant's crew) would have been in VOY's database (given that it would have been at least a month between then and VOY getting lost, I would hope that Janeway and some of her senior staff was at least briefed on it before she went to the Badlands and VOY's database updated).
I was just about to say this. Someone who was watching episodes with the captioning on claimed they read the caption "Borg Queen" for Jack's Mystery Voice, though.
If true, I honestly think it's a bit much. A little too much "small universe", but I can live with it.