When looking for a black hole, will we always find a collapsing star instead? I know that from the point of view of an outside observer, the collapse of a star into a black hole never finishes, i.e. any observer will always see a (red-shifted) version of the star before its collapse beyond the Schwarzschild radius. (See e.g. Can there exist an observer able to observe a collapse of a star into a black hole? and a few other questions on this site.)
Since this is true even for infalling observers getting arbitrarily close, does this imply that if we pick an object that we think of as a black hole originating from a star, and accelerate towards it with the intention of dropping into it, we will always see and hit the original star at a point where it is still larger than its Schwarzschild radius?
(If that is the case, how can we say that black holes "exist" in any meaningful sense other than as a mathematical limit?)
 A: 
Since this is true even for infalling observers getting arbitrarily close...

Arbitrarily close hovering observers will never see anything cross the horizon because of the extreme redshift, but infalling observers are different: they fall in. Proper time depends on the world-line, and different observers follow different world-lines, so "never" depends on which world-line we're talking about. The hovering observer never sees the infalling observer cross the horizon, but the infalling observer does.
Consider the Penrose diagram for a non-rotating black hole formed by a collapsing star in the context of classical general relativity:

In this diagram, diagonal lines represent lightlike directions. (Beware that this diagram distorts lengths and time intervals in order to make all diagonal lines correspond to lightlike directions. Representing a 4-d curved spacetime on a 2-d flat space requires making compromises!) The diagonal dashed line is the event horizon, and the horizontal line at the top is the central signularity. The diagonal lines labelled $\infty$ are in the infinite past and future, respectively. (Technically, these represent lightlike past and future infinity. The point where they meet represents spacelike infinity.) The lines labelled $r=0$ represent the center of spherical symmetry: each point in the interior of the Penrose diagram represents a whole sphere centered on $r=0$. Dashed lines can be crossed; solid lines cannot.
Now, consider the diagrams below, each of which shows the top part of the preceding Penrose diagram: 



*

*In the diagram on the left, the red line shows an infalling observer $A$ that hits the "surface" of the star just before it crosses the event horizon. The blue line represents light emanating from the collision event. The collision of $A$ with the star can be observed from the outside, albeit extremely redshifted (even though I drew it as a blue line), possibly into galactic-scale wavelengths if the collision occurs late enough. 

*In the middle diagram, the red line shows an infalling observer $B$ that hits the "surface" of the star after it crosses the event horizon. The blue line represents light emanating from the collision event. That light never escapes; it ends up hitting the singularity instead. For that reason, the collision of $B$ with the star cannot be observed from the outside: nothing that has crossed the event horizon can be observed from the outside. 

*The diagram on the right shows an observer $C$ that races inward but can't catch up with the collapsing star, because that observer's inward journey began too late. By the way, with the parameters depicted here, $C$ can see the light from $B$'s collision with the star (because the blue line from $B$'s collision intersects $C$'s red worldline), even though $C$ can't catch up with the star itself.

we will always see and hit the original star at a point where it is still larger than its Schwarzschild radius?

Always? No, not always. We can do that, if we start the journey soon enough (case $A$), but if we start later, then we won't be able to catch up with the star until after crossing the horizon (case $B$), and if we start too late, we won't be able catch up to it at all (case $C$).

Disclaimer: As mentioned near the top, this answer is based on classical general relativity. We know that classical GR isn't the final word, but we don't yet know exactly when/where/how it breaks down. These experiments with black holes have never been done, and nature is full of surprises!
