Adding memory often makes an entire system faster (again, because you can cache things in the faster RAM rather than paging out to disk). But for two comparable programs, I could see the argument that the lower-memory footprint program would be faster. (For comparable programs).
Often the memory being used is doing things like pre-loading information from disk or the network before it's needed, or caching results for reuse.
Or it's storing the information in a faster but less dense data structure - kind of like denormalizing a database for performance reasons.
Historically, under some circumstances, a problem compiled with -Os, may paradoxically be faster than -O2, and -O2 may be faster than -O3. I think the situation is getting better now, and the optimizing level mostly works as advertised. But there's still some problems in automatic loop vectorization.
The solution is to use abstract, arbitrary vectors in the ISA instead of packed SIMD and unrolled loops. RISC-V gets this right with their V extension.