This cannot happen as you describe in our standard $\Lambda$CDM cosmology. That is to say, the answer to
Is the answer simply that the first part of my question is wrong; that the light will in fact reach the other galaxy if that galaxy isn't currently moving away from us faster than the speed of light?
is "Yes". This doesn't mean Aslum's analogy is inaccurate; it could happen in principle in a different universe with a higher cosmological curvature or exotic matter with increasing energy density, just not in ours as we currently understand it.
There is certainly an upper bound to how far from us (measured according to the current notion of distance) a signal we send now will ever reach-- it's about $17$ billion lightyears-- but everything outside of this range is already receding faster than $c$. What's more, there are even points inside this range, i.e. that we can eventually get a signal to, that are currently receding faster than $c$.
The reason it can't happen is that the Hubble parameter is strictly decreasing (ignoring cosmological curvature), though it is leveling off. The distance between two (co-moving) fixed points in the FLRW spacetime is given by
$$D(t) = a(t) D_0 ,$$
where $D_0$ is the current (or co-moving) distance and $a(t)$ is the scale factor. The recessional velocity between these points is then
$$v_r = \dot{D}(t) = \dot{a}(t) D_0 = H(t) D(t),$$
where $H := \frac{\dot{a}}{a}$ is the Hubble parameter.
Now, if we emit a light signal toward a destination point $P$ at current distance $D_0$ as above with recessional velocity $v_r$ currently less than $c$, then after an infinitesimal time, the light will be closer to $P$ than $D_0$ because $v_r < c$. Similarly, as long as $P$ is receding from the position of the light at a velocity $v_r < c$ (it may well eventually recede from us much faster than $c$) the light will get closer to $P$.
If we define $R(t)$ to be the remaining distance to $P$ the light has to travel, then this says that $R(t)$ is strictly decreasing so long as $H(t)R(t) < c$. Now my former point comes up: $H(t)$ is decreasing as well, directly from the Friedmann equations! So if $H(t)R(t)$ is ever less than $c$ (as we've assumed it is initially), then both $H$ and $R$ are decreasing, so $H(t)R(t)$ remains less than $c$. Hence $R$ always decreases, and it will necessarily reach zero.
Addendum Regarding the "perspective" of light: this is a heuristic tossed around in introductory special relativity when discussing time dilation, but there's not much meaning to it. It should certainly not be taken to indicate light actually does anything instantaneously-- it only means that there is no meaningful notion of elapsed time intrinsic to the path light travels. This is distinguished from the case of the timelike paths obserservers can take, which have associated to them their proper time.
It also does not mean that one cannot cook up a reasonable (though highly coordinate-dependent) notion of elapsed time between two points in a spacetime (that may or may not happen to be connected by some light ray). The FLRW spacetime central to cosmology has sufficient symmetry that there's a very physically and geometrically natural choice of global coordinates that induce a notion of the "time" at which each point in spacetime occurs. This is the notion of time virtually universally discussed in the context of cosmology, especially in sources directed at laypeople. This time between two points is independent of any path connecting them, even if it is a path followed by light.
