Now that you mention it, I noticed this as well on my MBP 16 since yesterday after the update O only get the notification on my iPhone.
Apple just simply can't get this POS OS Catalina to work right, they fix one thing then they break basic functionality of other stuff!
They might as well ditch Catalina and start working on some new OS
Edit: After closing the Mail app and rebooting then relaunching it, I started getting notifications again.