But they don't. I see ads for installed apps all the time.

They could easily do this on device, but I still see ads for apps I own (including my own apps). Often right above the organic App Store search result for the same app