Wow. The "why" is a mystery to me (and, yes, senders should use the A record in the absence of an MX record). Just out of curiosity I looked up their SPF record.
Code:
safe-mail.net. 900 IN TXT "v=spf1 a mx a:orange.safe-mail.net a:pitango.safe-mail.net a:mango.safe-mail.net a:pop.safe-mail.net -all"
I find it interesting that orange, pitango, and mango all DO have MX records.