Years ago, Microsoft offered a free service called Windows Live Custom Domains (also known as Windows Live Admin Center) which allowed people who had their own domain name (such as myself with andrewtechhelp.com) to create a Windows Live Hotmail account with an email address that ended in that custom domain (such as spam@andrewtechhelp.com) instead of the usual @live.com address.
In 2014, Microsoft shut down the service and the associated admin portal, suggesting that people who still wanted this functionality switch to a paid Office 365 business plan (and they've since re-launched this type of service for individuals via Outlook.com Premium, but for a cost and only in the USA at this stage). However, for those of us already using Windows Live Custom Domains, they allowed the existing mailboxes that were already configured to continue working.
Starting in Office 2013, Microsoft also enabled Outlook.com users (the new name for Windows Live Hotmail) to start syncing their email, calendar and contacts with Outlook 2013, via a protocol called Exchange ActiveSync (support for this protocol was added in Outlook 2013). This protocol was not the same as the Exchange Web Services used by Outlook 2007/2010/2013 to sync email, calendar, contacts, tasks and notes with a Microsoft Exchange server, but it was the same protocol used to sync email, calendar and contacts to mobile devices such as iOS, Android and Windows Phone.
This all worked fairly well (the syncing between Outlook 2013 and Outlook.com was limited, but usable for basic needs) even for mailboxes that were created for custom domains, until 2016 when Microsoft started upgrading the infrastructure behind Outlook.com to move it to Office 365 based infrastructure (essentially cloud-hosted Microsoft Exchange servers). One of the changes this brings is that instead of using the Exchange ActiveSync protocol for syncing between Outlook 2013/2016 and Outlook.com, it now syncs using the Exchange Web Services protocol (Exchange ActiveSync is still used for mobile devices). There are many advantages to this (mainly full syncing support for all types of content including tasks and contact groups, plus support for Outlook 2016 for macOS).
Microsoft has been sending messages out to everyone syncing their Outlook.com accounts to Outlook 2013/2016 using the Exchange ActiveSync protocol to reconnect their account so that it starts using the Exchange Web Services protocol. However, if you have a mailbox that was created for a custom domain, you may not be able to get it to correct reconnect using the Exchange Web Services protocol.
The likely reason is that you're missing a DNS record that is required for the Exchange Autodiscover service. This is used to get the correct settings for a mailbox stored on a Microsoft Exchange server (which Outlook.com accounts now are) and provide them to Outlook 2013/2016. When you first configured your DNS records to enable Windows Live Custom Domains to work properly, they never included a step to add this record because it wasn't relevant back then, but it is now. Microsoft actually wrote some documentation up about this (https://support.office.com/en-us/article/Fixes-or-workarounds-for-recent-issues-on-Outlook-com-8c95d913-d96b-4065-9171-e1fa44b03ff5?ui=en-US&rs=en-US&ad=US), however (at the time of writing this) someone has copy and pasted the wrong table into the documentation, hence why I'm writing this post.
Under the section titled "Unable to configure Custom Domains accounts to connect in Outlook as an Exchange account", step 1 includes the following instruction: "Add a CNAME record to your DNS settings at your domain registrar. A CNAME record is needed for Outlook to configure the account using Autodiscover. The only record you need to add is for Host Autodiscover". However, the table below then talks about an MX record, which is not a CNAME record.
The correct information you need to add is the following:
Record Type: CNAME
Host: autodiscover
Points To: autodiscover.outlook.com
TTL: 1 hour (this option may not even be available or you may not be able to set it to 1 hour depending on your DNS provider. Just set it to the closest time to 1 hour if possible, remembering that many DNS providers have the TTL fields measured in seconds, not hours).
Step 2 is just verifying that your MX record is still configured correctly. If you can still send and receive email to this mailbox, then this MX record is correctly configured. It's highly unlikely that you'll need to change this.
All you need to do now is wait approximately 12-24 hours to ensure your DNS changes propagate out over the internet and you should now be able to add the mailbox for your custom domain to Outlook 2013/2016 using the Exchange Web Services protocol!
Update (27/01/2017): Microsoft has updated their documentation to fix their error. Hopefully this article is still an interesting look into the back story of this change though. Thanks to Mark in the comments for letting me know about Microsoft updating their documentation.