Obviously one can mathematically cook up equations of motion that would not arise from an action principle.
The original motivation for believing that Nature obeys a Law of Least Action was metaphysical, and then it turned out that in reality, one could only guarantee that the action was stationary, not necessarily minimal, which ruined the metaphysics... besides, one must be cautious about postulating that Nature has to do something which we have deduced based on philosophical motivations.
But ever since Hertz and Einstein, there has been another motivation. (Whether it will stand the test of time better than string theory, remains to be seen...)
Gauss, Hertz, and after them, Klein (see Whittaker, Analytical Dynamics, p. 254ff. and Hertz, The Principles of Mechanics, http://www.archive.org/details/principlesofmech00hertuoft ) reformulated Newtonian Mechanics in terms of an abstract curved space on which all particles followed geodesics. The metric on the space was cooked up from the forces acting on the system, and all the laws of mechanics reduced to Hertz's principle of least curvature instead of least action. Now after Einstein we know that if we interpret gravity as the metric of space-time, then particles under the influence of gravity follow a geodesic. This is a generalisation of the very old principle of inertia: with Newton it was stated as, a particle not acted on by a force travels in a straight line, i.e., a geodesic in flat Newtonian space. Einstein re-formulated this as above stated. The quest for a (non-quantum) unified field theory was always motivated by this: define a geometry on space-time based on the forces of Nature so that all trajectories will be geodesics. The physical insight here is the same as that underlying the original law of inertia: natural, unconstrained motion is straight, i.e., geodesic. But geodesics always do obey some variational principle.
If we take Einstein's point of view seriously, and think it will survive when treated quantum-mechanically, then the answer to your question would be: if the set of trajectories arise as the set of geodesics from some metric on the relevant space, then there is a physically significant action principle which governs the dynamics.