Back in TOS, it was a bit more vague: our heroes seemed capable of moving across the entire Milky Way at will, rather than having to spend 70 years in transit. But we can reinterpret most of those references to "the other side of the galaxy" as hyperbole, and pretend that Kirk moved just as slowly as Picard or Janeway.
Kirk's first adventure at the edge of Milky Way seemed to be some sort of a proof-of-concept mission to find out whether one can even leave our galaxy, not a serious attempt to explore what lies beyond. Many a thing in "Where No Man Has Gone Before" points to a short-term mission whose purpose was to deliberately steer into the barrier at the edge and see if one can get to the other side. It seems unlikely Starfleet back then ever seriously pondered sending a ship to a location outside the Milky Way, such as Andromeda or one of the neighboring non-spiral galaxylets.
Yet TOS also has an interesting bit about other galaxies in "The Alternative Factor": the spacetime tremors caused by the two Lazari are reported as having been observed at distant locations...
Admiral of the Week: "You're aware of the effect an hour ago."
Kirk: "Yes, Sir."
Admiral: "You may not be aware of its scope. It occurred in every quadrant of the galaxy and far beyond."
So it seems Starfleet is in chatting terms with observers "far beyond" Milky Way, or otherwise capable of seeing what happens out there. That sort of reach has not been suggested in any other episode, but it does open interesting possibilities.
Timo Saloniemi