This isn't a DNS issue - it is an issue with the way the web server is setup.
An SRV record isn't going to help, because it is further down the list of URLs that are tried by the Autodiscover process. Top of the list is the root of the domain which is what you are seeing. As you already have the Autodiscover.example.com DNS entry, then you have done everything you can do with DNS. SRV records come AFTER the two you already have.
The primary cause of this problem is the control panel used by the host - the most popular one attempts to use Autodiscover to configure its own email services. The web host needs to disable Autodiscover in the control panel for that domain. If you browse to the path then you will probably find there is something there. Autodiscover depends on there being nothing there.
I have also seen it happen when a custom 404 file is used, because if they aren't implemented correctly it basically means all URLs are valid - which will include the Autodiscover path. If you aren't using a control panel then this is the most likely cause of the problem.
Putting an XML file in to the path on the web server will simply generate prompts to allow redirection to take place which will cause support headaches for the internal support staff.
The best fix is to stop the URL from working at all so that Outlook moves on to the next URL - which will work fine.