The "inflexible approach to solving problems" you refer to has, as far as I can tell, nothing at all to do with "machines", except perhaps in an exceptionally abstract sense, in the form of virtual machines designed for thinking about. On the other hand, problem solving doesn't get much more flexible than raw assembly. My point stands.
I think the early adoption of imperative languages was more due to pragmatism than elegance[0]; at first, you had to stay close to the machine to get anything done, at first because that's all that existed (Fortran beat Lisp into existence by a year) and then for performance. Remember, Fortran was still basically a shortcut for assembly, while Lisp started as a purely mathematical abstraction, designed expressly for thinking about, that some goofball wrote an interpreter for.
[0] This principle is still clearly in force today. We wouldn't bother with C++ and JVM languages and Unix so much if pragmatism wasn't paramount.
I'm using Fortran as my example of an early imperative language. There might have been earlier ones (maybe a version of COBOL?), but since they were imperative it doesn't materially affect my point.
If unix had been created in LISP or ML, I believe we might be in the opposite position. Though that hinges on a LISP unix being as successful as the C one.
There are of course many other things it could have been, but these are the first that come to my mind.
As humans I think we need the ability to be messy and imprecise in order to be creative.
>The reason we tend to think in imperative terms is one of familiarity
That's debatable given that both approaches have been around for about the same length of time with different outcomes in terms of adoption.