I might be way off base here, but recently ios added "Settings -> Privacy and Security -> Security Improvements -> Automatically Install"

Might be just OS security updates, but I wonder if it works for apps too?

This is the most interesting idea imo; do you think it’s testable? For example: allow the installed app to persist, turn on notifications, do some stuff to let a queue drain. Then remove.

Agreed, this is an interesting idea. I just checked and offloading unused apps is disabled on my phone

I wonder if this app is also an “app clip” - the small size applets that can bypass download size restrictions (and maybe, because of that, other restrictions).

How big is the installed size, and can you go to settings and delete app data before deleting the app? You may also check to see if it’s installed on other devices connected to your iCloud account or if you have any devices you never disconnected including Apple Watch as they have a watch app.

My wife works for macrumors and she once found an incomprehensible HomeKit bug and we had an Apple engineer come to our house to diagnose (we lived nearby to Cupertino)

It turned out to be a bug in the legacy HomeKit after upgrading on the backend. Totally opaque to the end user.

In which case, perhaps the app doesn't correctly remove notifications on delete which would mean Headspace could be to blame?

There’s no indication to the developer or app when a deletion happens. We rely on the OS to clean it up.

We've already seen where iOS notifications was storing messages, so it does seem plausible that notifications are involved. Especially as the latest release patches the notifications issue used by law enforcement. It's possible something new was introduced, revealed, etc. The timing feels right