Exactly. I think the Algorithm Design Manual does more to directly train that kind of thinking than many books.

Now if you want theory, I continue to recommend Algorithm Design by Kleinberg and Tardos.

Mathematicians look for more elegant proofs of already proven theorems all the time. The earliest proof is usually not the simplest, nor the clearest, nor the easiest to generalize, nor <insert desideratum here>.

Similarly, I think there is scientific value in finding cleaner ways to implement known algorithms, prove their complexity bounds, etc. For example, one of my current projects is to provide total functional implementations of known data structures and algorithms (i.e., free of assertions and unreachable control flow points), and I have gained insight about these data structures and algorithms that I couldn't have possibly obtained from their published descriptions.