Outlook 2007 auto discover prompt, very random

Prompt 1: you don't have "autodiscover.domain.com" record in your domain. But you have a "DNS SRV record" this is the 4th check of autodiscover before giving error
So it's:
https://blogs.technet.microsoft.com/rmilne/2014/10/02/how-to-check-exchange-autodiscover-srv-record-using-nslookup/
https://www.experts-exchange.com/questions/27695648/SRV-record-and-Autodiscover-Exchange-2010.html

And the reason why you get the 2nd is that you need to login to the server so you can get the emails.

So you can check it here ( outlook autodiscover and AS autodiscover tests):
https://testconnectivity.microsoft.com

Solution: Set up autodiscover record in internal infrastructure (internal DNS) and remove any other public DNS from your internal DNS, you should set those as forwarders in DNS snap-in.

Thanks, but why aren't any other users having this issue? We have 40 users, just this one has the issue. They all do the exact same thing, set up the exact same way.

you need to use the outlook autodiscover tools and figure out why is happening this to that user and look for event viewer, something have to give you the lights of whats going on.

What Exchange server you running and is it part of your organization/domain?
If Exchange 2007/2010 run:

Get-Command ExSetup | ForEach {$_.FileVersionInfo} 

Select allOpen in new window

If Exchange 2013/2016 run:

Get-ExchangeServer | Format-List Name, Edition, AdminDisplayVersion

Select allOpen in new window

It's Exchange 2007 and yes, it is on the domain.

In addition to the above requested output, please provide results of:

Get-OabVirtualDirectory | fl server, Name, ExternalURL, InternalURL, *auth*
Get-WebServicesVirtualDirectory | fl server, Name,ExternalURL, InternalURL, *auth*
Get-EcpVirtualDirectory | fl server, Name, ExternalURL, InternalURL, *auth*
Get-ActiveSyncVirtualDirectory | fl server, Name, ExternalURL, InternalURL, *auth*
Get-OutlookAnywhere | fl server, Name, *hostname*, *auth*
Get-OwaVirtualDirectory | fl server, Name, ExternalURL, InternalURL, *auth*
Get-ClientAccessServer | fl Name,OutlookAnywhereEnabled, AutodiscoverServiceInternalUri
Get-ExchangeCertificate | fl FriendlyName, Subject, CertificateDomains, Thumbprint, Services, Issuer, *not*
Get-MapiVirtualDirectory | fl server, Name,ExternalURL,InternalURL, *auth*
Get-ClientAccessArray | fl
Get-OutlookProvider

Select allOpen in new window

Feel free to mask real FQDN, format output as CODE.
It will assist in addressing the problem.

That did it, thanks much.