Has celestial navigation been materially impacted by the imperfect nature of celestial reference frames over time? In this video on inertial reference frames, it is mentioned that the stars are humanity's best inertial reference frame: the earth experiences a subtle acceleration relative to the sun due to the earth's own orbit and rotation; therefore the earth is only roughly an inertial frame. But, the stars are relatively fixed, they say.

However, the stars in galaxies move relative to each other--I assume many with some sort of rotational velocity and therefore acceleration--and galaxies themselves are all slowly moving away from one another, perhaps even with centrifugal acceleration of their own.

Has this acceleration been great enough that humanity has needed to update navigational tools that rely on the assumption that stars are an inertial reference frame?

Is it possible that every observable object in the universe is in fact accelerating relative to an unobservable reference frame?
The best inertial frame is that which is comoving with the cosmic microwave background. There is a notable dipole in the microwave background, the result of the Solar system's motion relative to it. The invariance of this dipole provides evidence that the frame of the barycentre of the solar system is also a very good inertial frame. 

This is of no significance to navigation, either by the stars, or among the planets. 

Within the solar system, the sun's gravitation influence is dominant. While the sun is orbiting with the galaxy, a space probe is also orbiting the galaxy, and the variation in gravitation due to the galaxy is extremely small. Galactic tides are several orders less significant than photon pressure, various quadrupole effects or the influence of other bodies.