One of the "evils" of premature optimization is how much time you spend on the optimization vs. the benefit you get from it. If your goal is correctness and shipping fast and you're not memory constrained then spending time using the least amount of memory is a waste of time specifically because you want to ship fast.

Another interesting thing that happens is you don't necessarily know what form your actual optimizations will need to take. Later when your systems grow you discover the suboptimal parts you hadn't optimized for.

Very early on at Cloudflare I worked on part of the DNS infrastructure that took DNS records from the UI and got them in a state for actual authoritative serving. The system had been constructed anticipating Cloudflare having millions of customers with unique domains, but it had not been constructed for a single customer with a single domain with millions of records. This caused a periodic slow down in DNS record updating while the system churned on that one customer.

In a different job I worked on a piece of optimization software that needed to keep track of "node" A is reachable from node "B". This had been implemented as a matrix (literally a malloced NxN matrix of ints storing 0 or 1) which worked really well for small systems. But you'd be out of memory really fast on a large project. I replaced the matrix with a hash table and all was good because the matrix was actually really sparse.

Engineers are expensive, especially good system engineers who are trained in your code base. Very possible that this just hadn't gotten to the top of the priority list.