Unable to send emails to external non-gmail accounts

Since Friday morning our organization has been getting bounce backs on all email sends not within the company, @godaddy.com (provider for Office 365) and @gmail.com accounts.  I have gone through the process of "fixing" the SPF and DNS, waited over 24 hours for propagation, called Go Daddy again, made additional changes, another 24 hours later still no joy.  

GD now says it's a Microsoft issue and they are working on fixing it...anyone else having issues?  We've been 4 full days now not being able to send emails to clients and prospective clients.  Our business is being crippled.