How do certain apps show new notifications when internet access is restricted to them?

App developers can tell better but what I perceive is that many modern apps use Firebase Cloud Messaging - a proprietary service from Google, not part of AOSP - for push notifications. In fact developers are forced to use Google's proprietary products unnoticeably. Quoted from here:

The Doze restriction on network access is also likely to affect your app, especially if the app relies on real-time messages such as tickles or notifications. If your app requires a persistent connection to the network to receive messages, you should use Firebase Cloud Messaging (FCM) if possible.

...

FCM is optimized to work with Doze and App Standby idle modes by means of high-priority FCM messages.

FCM is a part of Google Play Services ⁽¹⁾:

FCM SDK's only hard dependency is Google Play Services

Play Services is a set of apps which are injected to Android devices with highly privileged permissions, so they aren't subject to data/battery restrictions.

Since you have blocked only the app and not Play Services, app may receive push notifications (though the actual data may not be delivered to the app).

So block GMS in order to block push notifications. Or choose the apps which aren't fond of Google.

RELATED: What is the exact functionality of Google Play Services & Services Framework?