Oooh, I see now!
So, it seems the background script gets executed each time it starts running again.
The problem in my case was that I do some async storage initialization and only after that I register the listener to listen to messages from elsewhere.
The fix then is: Register the listener in the background script right away (sync) and not postponed (i.e. after an async op).
Side note: The async initialization stuff shouldn’t even be executed multiple times during a single browser session -> can be safely moved to the callback of chrome.runtime.onInstalled.addListener.