Apps installed through Self Service re-appearing after device erase

Is your distribution method set to "Make Available in Self Service"? Are you removing the app when MDM profile is removed?

The apps are listed as "Make available in Self Service" and I do have the check to remove the app when the MDM profile is removed, however in our case, we are not removing the MDM profile....I mean not explicitly....we're just doing a "Erase all content and settings" on the device.

@sstoddard Are the devices supervised? When you "Erase all content and settings", do you need to re-approve the MDM?
We don't wipe our checkout iPads each time they get turned in, so I am not entirely sure how it behaves with a content wipe.
Are you making the apps managed?
I am going to perform a test with one of ours and see how it behaves.

edit:
I did an "Erase content and settings", MDM profile is gone, Supervision is gone, and all the apps are gone.

Yes, the devices are supervised. No, we don't seem to see a "re-approve" for the MDM...I mean, when going through the setup the next time it does show the "remote management" screen for the MDM, but nothing at all when erasing....just enter passcode and tap erase twice.

Yes, making the apps managed. (In my test case, I'm just using YouTube app as an example and bought 1000 of them through the VPP to use as deploy licenses.)

I didn't even get a "Remote Management" screen during the setup assistant, all the VPP apps are gone too.
Are you signing in with an Apple ID at any point?

Hmmm...weird. No. I thought it was just default behaviour that if you erase all content and settings it is still part of the MDM...wouldn't want users to be able to do this on their own.

So the MDM definitely gets it and the prestage is run on the setup after the erase. Just that the YouTube app keeps coming back.

I think the reason why it didn't pick up management is that we are out of licenses, even though it was enrolled and just needs to be re-enrolled. Maybe if I delete the old record it'll pick up enrollment, but at the moment I can't do further debugging.

Edit: I followed your workflow exactly, Erase Content and Settings -> Setup Assistant -> Accept Remote Management (we skip all setup options except Location Services). Boots to home screen, no additional apps were installed. Within ~3 minutes Self Service was deployed along with the 2 apps we have set to install automatically. The test app that I have configured for Self Service was not reinstalled after the reset. My last thought is maybe you have something set differently in your VPP configuration or in a configuration profile?