Typical that I figure out a fix after posting. Doing a little deeper searching (for notification issues on this discuss), what ended up working was clearing the caches for GPS and fastmail app. Once done, I have put Fastmail into optimised and the notifications are appearing now.
I also found a post saying that the firebase URLs should be allowed if you are filtering those. This doesn't make any difference either way.