U+M = a short script is easy to understand and can be quickly modified in small ways to test things or meet new requirements, but lack of reusable abstractions makes big or numerous changes harder and more time consuming
U+R = a longer program that uses an abstraction (classes, functions, modules, etc) is understandable and has many reusable components, but accounting for changes requires adding new components. This means the code isn't very malleable because you have to write all the interactions and containers and other stuff that lets new code connect and work in the abstraction.
R+M = finally, a fully abstract and malleable system, full of components and connectors and design patterns and such, can be readily adapted to changing requirements because it has high abstraction yet is factored deeply enough to allow small changes without lots of code. However, making changes requires understanding the entire system, damaging readability/understanding.
I don't think the problem is hopeless though. Usually when I see this, it's either because the problem domain is just that complicated, or because the system is actually too flexible for the scope of the problem. Sometimes a different abstraction can clear things up, because the old system was using too much of a poor abstraction to make it work.
In this instance, the last paragraph contains the real problem and hints towards a solution:
> If I’m trying to run five different deploy recipes across four different hardware/OS configurations, that’s 20 different potential interactions to take care of.
I forgot the name of the problem now, but Peyton-Jones talks about this with regards to how OOP and FP tend to hit opposite sides of these problems. OOP makes it easy to add new objects but hard to add methods because you have to add it to every object. FP makes it easy to add pattern-matching functions, but hard to add new objects because each function has to account for the new objects.
Something like multiple dispatch is the usual solution: one function for each combination of things, with shared functions factored out as needed. The OOP version, the visitor pattern, falls afoul of being hard to understand, imho.