I’m not sure if Go Daddy provides DNS hosting for domains that are not registered with them. But you could try to move your domain’s DNS hosting to a provider that does, like Cloudflare.
All I can say for certain based on the messages from you and @visuidesign is that Microsoft seems to have trouble looking up MX records with domains hosted with us.
But I just tried it myself using an Outlook.com account and a few different domains hosted here, and didn’t run into any issues.
So I really have no idea what could be the issue. I can’t reproduce any of the issues you’re having.