Thanks for the pointer to the Ehlers paper, atyy -- that's cool.
I would respond to that question by being weasely :-) Physics isn't math, and physical theories aren't axiomatic systems. The physical principles behind GR (the equivalence principle, ...) have resisted precise mathematical formulation, and maybe they always will. The theorem in the Ehlers paper isn't a general theorem in GR; it's a theorem about certain types of physical systems -- those that obey the dominant energy condition and are nonsingular. (The latter isn't explicitly stated in the paper, but I think it's implicit, since they assume the metric is well defined in a certain neighborhood.) We have strong reasons to believe that there are physical systems that violate the DEC (
http://arxiv.org/abs/gr-qc/0205066v1 ), and that there are also physical systems that are singular. What I would say is that if we came across a real-world physical system (a singular one, or one that violated the DEC) for which there was no result conceptually analogous to the theorem in the Ehlers paper, then that would falsify GR's geometrical picture of gravity.
I think the first two paragraphs on p. 2 of the Ehlers paper do a good job of explaining why this question doesn't have a well-defined answer unless the terms are more clearly defined.
If you want a specific example where bodies of finite mass clearly don't travel along geodesics, then replace one of the neutron stars in the Hulse-Taylor binary with a black hole. In this situation we can't possibly talk about whether the black hole follows a geodesic of the full metric, since in that spacetime the singularity isn't a point in the manifold; all we can hope to say is whether the black hole follows a geodesic of the background metric. It is then clear that it can't follow a geodesic of the background metric, since the rate of radiation is proportional to the square of the mass of the black hole.