I wonder if it is an SPF (Sender Policy Framework) failure?
I don't know a huge amount about this, and I would have though the powers that be at Facebook would, but it seems to me that the server I receive notifications from does not have permission to send email from Facebookmail.com.
I have check the DNS records for facebookmail.com and the allowed mail servers under SPF are 188.8.131.52, 184.108.40.206 and 220.127.116.11
However, the IP address I get emails from on this domain is 18.104.22.168. I got this by checking the headers of the emails.
I then checked how googlemail sees this, and sure enough there is this error:
Received-SPF: softfail (google.com: best guess record for domain of transitioning email@example.com does not designate 22.214.171.124 as permitted sender) client-ip=126.96.36.199;
So google mail is saying there is an SPF failure here, which googlemail treats as a soft fail.
Maybe other email providers see this as a hard fail, and so no emails.
Just my 2 minutes of investigation.
Pass it on to Facebook. Invoice is in the post.