EDIT: highlight required trailing dots + added CNAME for msoid.
If you're using a hosting provider which uses DirectAdmin for its DNS management, it may be a hassle to correctly configure DNS records for Office 365, mainly because of syntax issues. After some trial-and-error and googling, I finally managed to correctly devise the proper syntax to configure Exchange Online and Lync Online.
The set up of the entries below is a left and right field in the DNS management, safe for MX-records, which are set up elsewhere. For most services, don't forget to add the trailing . at the end of each record pointing to a Microsoft Server. Otherwise, resolving will incorrectly add your own do ...