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 69.63.178.128, 69.63.184.0 and 66.220.144.128
However, the IP address I get emails from on this domain is 69.63.178.173. 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 notification+m-h3ki1d@facebookmail.com does not designate 69.63.178.173 as permitted sender) client-ip=69.63.178.173;
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.