I'm not convinced it would be so hard. I imagine something like ForegroundToken's:
Activities (now plural with multi-window) in the foreground (onResume) gain access to a ForegroundToken. The service requests require you to pass in the ForegroundToken. This token is then validated at the moment of the request.
When the app goes into the background the system invalidates the token, so any work waiting in queue somewhere will actually fail on the token check when it comes up.
If you want to ask a background service (of your own), or fire off an intent, you pass the ForegroundToken with it. If the work starts while your app is still in the foreground peachy, if not, it fails.
In a foreground > background > foreground cycle, your app gets a new ForegroundToken on every onResume event.
If you want apps to have true background access to a permission, that is a separate toggle (yes more complicated I know, but theoretically possible). They then can pass null into the ForegroundToken argument.