Problems connecting to Exchange Server 2013 via Outlook 2007

What is the issue you are having.  Outlook 2007 SP3 or higher is supported as per MS.

Nope. Outlook 2007 works fine with Exchange 2013. I would recommend however, that it is fully patched.

What are the errors?

It discovers the server then kicks this on  the third checkbox.

The connection to Microsoft Exchange is unavailable. Outlook must be online or connected to complete - Cant add Outlook accounts

Yes 2010 and 2013 Outlook works fine. I checked the certificate and that seems to be fine.

Help

Is Outlook 2007 fully patched?

yes

I also cannot connect via my phone's email client. Android. No error except cannot establish connection.

See attached for my  DNS settings

Try running the ActiveSync test at WWW.EXRCA.COM and see what you get.

<?xml version="1.0" encoding="utf-8"?>
<testresult status="FatalError" errorid="734044ef-11c2-4e30-9ee6-450d49e9d92c" contentUrl="" testdescription="The Microsoft Connectivity Analyzer is testing Exchange ActiveSync. " resultdescription="The Exchange ActiveSync test failed." additionaldetails="" elapsedMilliseconds="2362">
  <children>
    <testresult status="FatalError" errorid="734044ef-11c2-4e30-9ee6-450d49e9d92c" contentUrl="" testdescription="Attempting the Autodiscover and Exchange ActiveSync test (if requested)." resultdescription="Testing of Autodiscover for Exchange ActiveSync failed." additionaldetails="" elapsedMilliseconds="2359">
      <children>
        <testresult status="FatalError" errorid="734044ef-11c2-4e30-9ee6-450d49e9d92c" contentUrl="" testdescription="Attempting each method of contacting the Autodiscover service." resultdescription="The Autodiscover service couldn't be contacted successfully by any method." additionaldetails="" elapsedMilliseconds="2359">
          <children>
            <testresult status="Error" errorid="734044ef-11c2-4e30-9ee6-450d49e9d92c" contentUrl="" testdescription="Attempting to test potential Autodiscover URL https://mydomain.com:443/Autodiscover/Autodiscover.xml" resultdescription="Testing of this potential Autodiscover URL failed." additionaldetails="" elapsedMilliseconds="351">
              <children>
                <testresult status="Success" errorid="00000000-0000-0000-0000-000000000000" contentUrl="" testdescription="Attempting to resolve the host name mydomain.com in DNS." resultdescription="The host name resolved successfully." additionaldetails="IP addresses returned: 23.238.21.24" elapsedMilliseconds="72">
                  <children />
                </testresult>
                <testresult status="Success" errorid="00000000-0000-0000-0000-000000000000" contentUrl="" testdescription="Testing TCP port 443 on host mydomain.com to ensure it's listening and open." resultdescription="The port was opened successfully." additionaldetails="" elapsedMilliseconds="93">
                  <children />
                </testresult>
                <testresult status="Error" errorid="734044ef-11c2-4e30-9ee6-450d49e9d92c" contentUrl="" testdescription="Testing the SSL certificate to make sure it's valid." resultdescription="The SSL certificate failed one or more certificate validation checks." additionaldetails="" elapsedMilliseconds="185">
                  <children>
                    <testresult status="Error" errorid="e477b71e-06fb-4dfe-a64c-0355e8b67772" contentUrl="" testdescription="The Microsoft Connectivity Analyzer is attempting to obtain the SSL certificate from remote server mydomain.com on port 443." resultdescription="The Microsoft Connectivity Analyzer wasn't able to obtain the remote SSL certificate." additionaldetails="The certificate couldn't be validated because SSL negotiation wasn't successful. This could have occurred as a result of a network error or because of a problem with the certificate installation." elapsedMilliseconds="128">
                      <children />
                    </testresult>
                  </children>
                </testresult>
              </children>
            </testresult>
            <testresult status="FatalError" errorid="734044ef-11c2-4e30-9ee6-450d49e9d92c" contentUrl="" testdescription="Attempting to test potential Autodiscover URL https://autodiscover.mydomain.com:443/Autodiscover/Autodiscover.xml" resultdescription="Testing of this potential Autodiscover URL failed." additionaldetails="" elapsedMilliseconds="1979">
              <children>
                <testresult status="Success" errorid="00000000-0000-0000-0000-000000000000" contentUrl="" testdescription="Attempting to resolve the host name autodiscover.mydomain.com in DNS." resultdescription="The host name resolved successfully." additionaldetails="IP addresses returned: 174.79.71.246" elapsedMilliseconds="150">
                  <children />
                </testresult>
                <testresult status="Success" errorid="00000000-0000-0000-0000-000000000000" contentUrl="" testdescription="Testing TCP port 443 on host autodiscover.mydomain.com to ensure it's listening and open." resultdescription="The port was opened successfully." additionaldetails="" elapsedMilliseconds="119">
                  <children />
                </testresult>
                <testresult status="SuccessWithWarnings" errorid="734044ef-11c2-4e30-9ee6-450d49e9d92c" contentUrl="" testdescription="Testing the SSL certificate to make sure it's valid." resultdescription="The certificate passed all validation requirements." additionaldetails="" elapsedMilliseconds="395">
                  <children>
                    <testresult status="Success" errorid="00000000-0000-0000-0000-000000000000" contentUrl="" testdescription="The Microsoft Connectivity Analyzer is attempting to obtain the SSL certificate from remote server autodiscover.mydomain.com on port 443." resultdescription="The Microsoft Connectivity Analyzer successfully obtained the remote SSL certificate." additionaldetails="Remote Certificate Subject: CN=mail.mydomain.com, OU=Domain Control Validated, Issuer: CN=Go Daddy Secure Certificate Authority - G2, OU=http://certs.godaddy.com/repository/, O=&quot;GoDaddy.com, Inc.&quot;, L=Scottsdale, S=Arizona, C=US." elapsedMilliseconds="301">
                      <children />
                    </testresult>
                    <testresult status="Success" errorid="00000000-0000-0000-0000-000000000000" contentUrl="" testdescription="Validating the certificate name." resultdescription="The certificate name was validated successfully." additionaldetails="Host name autodiscover.mydomain.com was found in the Certificate Subject Alternative Name entry." elapsedMilliseconds="1">
                      <children />
                    </testresult>
                    <testresult status="SuccessWithWarnings" errorid="734044ef-11c2-4e30-9ee6-450d49e9d92c" contentUrl="" testdescription="Certificate trust is being validated." resultdescription="The certificate is trusted and all certificates are present in the chain." additionaldetails="">
                      <children>
                        <testresult status="Success" errorid="00000000-0000-0000-0000-000000000000" contentUrl="" testdescription="The Microsoft Connectivity Analyzer is attempting to build certificate chains for certificate CN=mail.mydomain.com, OU=Domain Control Validated." resultdescription="One or more certificate chains were constructed successfully." additionaldetails="A total of 1 chains were built. The highest quality chain ends in root certificate CN=Go Daddy Root Certificate Authority - G2, O=&quot;GoDaddy.com, Inc.&quot;, L=Scottsdale, S=Arizona, C=US." elapsedMilliseconds="36">
                          <children />
                        </testresult>
                        <testresult status="Warning" errorid="1339c33a-8f21-427b-a323-4cee1a13f517" contentUrl="" testdescription="Analyzing the certificate chains for compatibility problems with versions of Windows." resultdescription="Potential compatibility problems were identified with some versions of Windows." additionaldetails="The Microsoft Connectivity Analyzer can only validate the certificate chain using the Root Certificate Update functionality from Windows Update. Your certificate may not be trusted on Windows if the &quot;Update Root Certificates&quot; feature isn't enabled." elapsedMilliseconds="5">
                          <children />
                        </testresult>
                      </children>
                    </testresult>
                    <testresult status="Success" errorid="00000000-0000-0000-0000-000000000000" contentUrl="" testdescription="Testing the certificate date to confirm the certificate is valid." resultdescription="Date validation passed. The certificate hasn't expired." additionaldetails="The certificate is valid. NotBefore = 10/7/2014 8:16:33 PM, NotAfter = 10/7/2015 8:16:33 PM" elapsedMilliseconds="0">
                      <children />
                    </testresult>
                  </children>
                </testresult>
                <testresult status="Success" errorid="00000000-0000-0000-0000-000000000000" contentUrl="" testdescription="Checking the IIS configuration for client certificate authentication." resultdescription="Client certificate authentication wasn't detected." additionaldetails="Accept/Require Client Certificates isn't configured." elapsedMilliseconds="418">
                  <children />
                </testresult>
                <testresult status="FatalError" errorid="734044ef-11c2-4e30-9ee6-450d49e9d92c" contentUrl="" testdescription="Attempting to send an Autodiscover POST request to potential Autodiscover URLs." resultdescription="Autodiscover settings weren't obtained when the Autodiscover POST request was sent." additionaldetails="" elapsedMilliseconds="895">
                  <children>
                    <testresult status="FatalError" errorid="6c458392-3a8c-4bc2-942e-7ab533744106" contentUrl="" testdescription="The Microsoft Connectivity Analyzer is attempting to retrieve an XML Autodiscover response from URL https://autodiscover.mydomain.com:443/Autodiscover/Autodiscover.xml for user vducote@mydomain.com." resultdescription="The Microsoft Connectivity Analyzer failed to obtain an Autodiscover XML response." additionaldetails="An HTTP 401 Unauthorized response was received from the remote Unknown server. This is usually the result of an incorrect username or password. If you are attempting to log onto an Office 365 service, ensure you are using your full User Principal Name (UPN).&#xD;&#xA;HTTP Response Headers:&#xD;&#xA;request-id: c8a98a2a-54d2-4c42-9718-ca774307c23d&#xD;&#xA;Server: Microsoft-IIS/8.5&#xD;&#xA;WWW-Authenticate: Negotiate,NTLM,Basic realm=&quot;autodiscover.mydomain.com&quot;&#xD;&#xA;X-Powered-By: ASP.NET&#xD;&#xA;X-FEServer: MYDOMAIN02&#xD;&#xA;Date: Wed, 08 Oct 2014 17:07:20 GMT&#xD;&#xA;Content-Length: 0&#xD;&#xA;" elapsedMilliseconds="894">
                      <children />
                    </testresult>
                  </children>
                </testresult>
              </children>
            </testresult>
            <testresult status="Warning" errorid="c0f75b77-072c-48d5-ab17-eebc99a4b3d9" contentUrl="http://go.microsoft.com/?linkid=9843786" testdescription="Checking if there is an autodiscover CNAME record in DNS for your domain 'mydomain.com' for Office 365." resultdescription="Failed to validate autodiscover CNAME record in DNS. If your mailbox isn't in Office 365, you can ignore this warning." additionaldetails="There is no Autodiscover CNAME record for your domain 'mydomain.com'." elapsedMilliseconds="28">
              <children />
            </testresult>
          </children>
        </testresult>
      </children>
    </testresult>
  </children>
</testresult>

Are other versions of Outlook working fine? Or is 2007 all your have in the environment?

 If all Outlook clients, could be an issue with the autodiscover URLs or certificates. Or even the DNS entries internally.
http://supertekboy.com/2014/07/08/designing-simple-namespace-exchange-2013/ 

Gareth after following those steps, we cannot access our web site internally. Its accessible outside of the network but not internally. Web site is still hosted off site.

Are you referring to your externally hosted website? For example www.mycompany.com?

If so, and it was after you did the split-brain DNS, you will also need to add a WWW A record to that split-brain zone on your internal DNS server. And then point it to the external IP of your website. Once you do that, you should be able to get to your website from inside your network.