Luckily I have lots of stuff in Azure cloud so I can start up a support ticket using one of my o365 tenants. Getting support directly for personal office 365 subscriptions is probably an even bigger nightmare.
I've created a ticket, and we are scheduled to talk on the phone on Tuesday. Of course in the meantime he sent me the troubleshooting website for outlook search, so I'm not super optimistic, especially if Microsoft isn't making their techs aware. I included this thread and also the bulletin, but there was no mention.
I have many clients with this issue, and I know I have a long road ahead of me if Microsoft is forcing me to get this fixed starting at square one. abdias_ruiz we would appreciate if you could work on this, as you probably have more power to move this forward than we do working with your support techs.
Thank you again for helping us in the thread!