For example, with Scala simple Arrays outperform most other collections, including Vectors and Lists, even when the big O is bad.
Array languages are especially powerful, even though algorithms implemented in them often do a lot of extra work. If you can keep all of your data in L1, it doesn't much matter what big O you have (usually) and the most naive data structures and algorithms will usually outperform fancy pointer chasing stuff in L3 or RAM.
4) Realizing that there is a Big O around the larger architecture and thinking it is always important
5) Realizing that archecture is determined by the problem space, so addressing the problem itself as directly as possible will converge on optimal Big O
Once you've done it over and over for years it becomes more clear how Big O just reflects the assumptions, and fighting it at the terminating point of the specific algorithms and data is a thing to defer until an easy win is needed. The only effort greenfield code deserves for optimization, OTOH, is to quickly review the language's built-in structures, and pick the one that is approximately best. Push the features, then as time permits build profiling mechanisms to find the hotspots as the system gets production data.
1) Not knowing
2) Knowing Big O and thinking it is always important
3) Knowing Big O and realizing constants matter in practice so you stop optimizing prematurely
Anyway, that was my evolution. I agree with most of what you say except I think I would change complex algorithm to complex data structure.