Okay, after much experimentation, it seems like I have a strong suspect now among my extensions. Now I've only disabled this Flash Video Downloader: https://chrome.google.com/webstore/detail/flash-video-downloader/aiimdkdngfcipjohbjenkahhlhccpdbc?hl=en-US
And since that, notifications started to get through. I don't know how I've missed it earlier, but this seems to be the culprit. I just leave this here as future reference, I guess I'm not the only one using this extension in Opera...