So I’ve tried uninstall the app, cleared all data and cache and resintalled it - nothing worked.
For some reason, pressing and holding the notification brought up the notification setting menu.
It seems these notifications are marked as ‘Other’ and not critical by the phone notification service:
Changing it to ‘Important’ fixed it - Not sure why was it marked as ‘Other’ in the first place.
UPDATE:
It seems I need to change this setting for each notification channel - Pretty annoying - I wish I could understand why are these notification marked as ‘Other’ by default.