Excellent post. Thanks for writing down formally and elaborating how this is not an easy problem to solve.
Curious to know if there is data on how optimal the current mined blocks are? I presume this is hard to do exactly because out of band transactions and inconsistent mempools.