In the first season ep "Unexpected" they encountered aliens who had a holodeck. That's it. But apparently it's impossible that anyone had holo tech before TNG...
I think the issue here is that the NX-01 encounters an advanced alien race with holodeck technology back in the 22nd century, but by the 24th (specifically the first season of TNG), holodeck technology is treated as if it's brand-new to the entire Federation and Starfleet.
Just like how Archer saw Ferengi 200 years before Picard made "first contact" with them. Their excuse was that Archer never actually knew the name of their race, but that didn't really matter, because we the audience knew damn well who they were. The Borg too. Suspension of disbelief just seemed to fall apart after awhile.