Thanks guys, I figured this out myself, there is indeed an issue with the DNS and or the MX record, the domain name actually exists and is registered according to http://whois.ausregistry.net.au/
Whatever the issue, the value is formally a correct email address, and this is a real order processed offline/different system, and we can’t push it to Shopify because of the error.
I was hoping the Shopify people will explain the validation or point me to the docos.
As it is, I wouldn’t call this a feature, really.
Thanks again, James and Jason for your time.
Cheers,
Radu