The only reason of warning you see “sender fail fraud detection” in your outlook while sending or replying a mail to another domain, could be that the other domain doesn’t have the valid/existence of a “include” record or etc. in their SPF record. Thus, authentication fail.
To resolve this is to add the missing particular record to your SPF record;
Example:
Actual;
v=spf1 ip4:192.168.1.1 ipv4:192.168.1.2 mx ~all
Expected;
v=spf1 include:spf.protection.outlook.com ip4:192.168.1.1 ipv4:192.168.1.2 mx ~all
*Note: This will take up to 24 hours for the record fully propagated. There is not much differences for your “all” with symbol of “~”, “-“, or “?”. After propagated, make use of this online DNS checking tool called “mxtoolbox” to make sure the record is correct.
If after adding/modifying your SPF record, and you still having trouble with it, is best that you check with your hosting company and raise a case to Microsoft Office 365 support for further assistance.
Sabrina Kay's Blog 