I think the fundamental problem with OS-level ads is that they're by design irrelevant. I don't mind Google search ads because I'm searching for something related.

But in the OS, if I'm opening the start menu, my intention could be anything. Microsoft is then forced to serve the most generic ad possible, which is going to be irrelevant 99% of the time.