A substitution is a very general procedure in mathematics. Your students will have experienced it many times already in algebra before they got to calculus, e.g., when solving two equations in two unknowns. More generally, it's an example of a change of variables, in the case where there is only one variable. An example in two variables would be changing from coordinates $(x,y)$ to new coordinates $(u,v)=(y,-x)$, i.e., a 90-degree rotation. As a fancy example from an advanced subject, you could look at the transformation from Schwarzschild coordinates to Kruskal-Szekeres coordinates for a black hole.
It's often convenient to do a change of variables simply for convenience of notation. For example, if I was going to do a lengthy calculation involving a cylindrical tank, I might find it useful to switch from the radius to the cross-sectional area, just to keep the writing simpler.
So the attitude should be simply that substitutions are things that we do naturally whenever it's convenient. They make life better by keeping things simpler. Who wants to make things hard?
Even within the context of freshman calculus, there are plenty of cases where your students' pattern-recognition strategy won't work, e.g., $\int dx/\sqrt{1-x^2}$.
As an example where you really, really want to do some substitutions, consider the problem of finding the magnetic field inside a solenoid of finite length, by integrating over loops of current. This gives an integral of the form $B=\int_p^q a^2(a^2+z^2)^{-3/2} dz$. Students should be taught that the very first thing to do here is the substitution $u=z/a$, simply because it cleans up the integral. After that, the substitution $\tan\theta=1/u$ makes the integral into a trivial one. Moreover, the final result is simpler when expressed in terms of $\theta$ than in terms of $z$, so it should just be left that way. And $\theta$ also has a direct geometrical interpretation.
A similar example would be something like $\int_{-\infty}^\infty a^2(a^2+z^2)^{-3/2} dz$. It should be explained to students that this is an indefinite integral, not a definite integral, and that the first step should be to make it into a definite integral with the substitution $u=z/a$. In real-life applications, this type of substitution is almost always obvious because we want to change from a variable that has units to one that is unitless.
IMO the term "$u$-substitution" should be dropped. We should just call this a substitution or a change of variables. That would make it more clear that this is just a normal and familiar mathematical practice. Furthermore, it would disabuse students of the notion that they will never have to make up their own notation for a change of variables -- something they are incredibly reluctant to do, because in general, they are almost never asked in a math course to make up notation for something.