this is exactly what "higher" compression levels do (among other things like bigger dictionary) - they try harder, more iterations, to find the optimum combination of available knobs for a particular chunk of data.
Yes, that much was always clear. I just always thought the way these software go about finding those combinations was also standardized on a high level rather than proprietary to each implementation. It is a fairly recent development for me to realize that the various encoder options and presets are specific to the encoder, not the format (and now, that the same is true for lossless formats too).
for video there is another constraint - time
hardware encoders (like the ones in GPUs) typically work realtime-ish, so they do minimal exploration of encoding space
you also have the one-pass/two-pass thing which is key for unlocking high quality compression
Makes a lot of sense in retrospect, to the extent it bothers me I haven't figured it out myself earlier.