classical mechanics - Why the Principle of Least Action?

I'll be generous and say it might be reasonable to assume that nature would tend to minimize, or maybe even maximize, the integral over time of $T-V$. Okay, fine. You write down the action functional, require that it be a minimum (or maximum), and arrive at the Euler-Lagrange equations. Great. But now you want these Euler-Lagrange equations to not just be derivable from the Principle of Least Action, but you want it to be equivalent to the Principle of Least Action. After thinking about it for awhile, you realize that this implies that the Principle of Least Action isn't really the Principle of Least Action at all: it's the "Principle of Stationary Action". Maybe this is just me, but as generous as I may be, I will not grant you that it is "natural" to assume that nature tends to choose the path that is stationary point of the action functional. Not to mention, it isn't even obvious that there is such a path, or if there is one, that it is unique.

But the problems don't stop there. Even if you grant the "Principle of Stationary Action" as fundamentally and universally true, you realize that not all the equations of motions that you would like to have are derivable from this if you restrict yourself to a Lagrangian of the form $T-V$. As far as I can tell, from here it's a matter of playing around until you get a Lagrangian that produces the equations of motion you want.

From my (perhaps naive point of view), there is nothing at all particularly natural (although I will admit, it is quite useful) about the formulation of classical mechanics this way. Of course, this wouldn't be such a big deal if these classical ideas stayed with the classical physics, but these ideas are absolutely fundamental to how we think about things as modern as quantum field theory.

Could someone please convince me that there is something natural about the choice of the Lagrangian formulation of classical mechanics (I don't mean in comparison with the Hamiltonian formulation; I mean period), and in fact, that it is so natural that we would not even dare abandon these ideas?