How do I get Autodiscovery to work?

Hi Everyone,
I really am posting here as a last resort. I've looked at a number of other posts regarding this issue, have followed FAQ's and walkthroughs and all sorts, but i'm drawing a blank.

I am having continued problems getting Autodiscover to work internally and externally. Let me give you my configuration.

I have a single Exchange 2007 server
I have a trusted ssl certificate for mail.domain.com
I have modified the internal and external urls on all of the ex2007 web services.
The cert is installed into IIS correctly, I can run 'Get-ExchangeCertificates' and I am shown my mail.domain.com certificate as the top option, it has a status of enabled and the RootCAType is ThirdParty.
my IIS has the cert set as it's port 443 binding certificate.
I created a new internal primary zone in DNS for my internet domain and i've configured an A record to direct mail.domain.com to my local exchange server ip.
I've modified my external mail.domain.com dns record to pass port 443 through to the exchange server IP
I have created an internet based SRV record to point to my Exchange server.
I have set up autodiscover.domain.com to direct to my exchange server.

When I run Test-OutlookWebServices -identity test.user I am given a glowing report saying that everything has been a "sucess". So on the surface things look good.

However, If I browse manually to https://mail.domain.com/autodiscover/autodiscover.xml on one of my domain pc's I get a small popup advising asking me if I want to use a particular certificate, which is NOT my TrustedSSL third part cert. it's a self signed local certificate. If I select OK to use it, I am shown the XML output:

  <?xml version="1.0" encoding="utf-8" ?>
- <Autodiscover xmlns="http://schemas.microsoft.com/exchange/autodiscover/responseschema/2006">
- <Response>
- <Error Time="11:27:06.0812428" Id="2799226687">
  <ErrorCode>600</ErrorCode>
  <Message>Invalid Request</Message>
  <DebugData />
  </Error>
  </Response>
  </Autodiscover>

If I browse to https://mail.domain.com/EWS/Exchange.asmx I am given a large output of XML and it seems to work fine.

IF I browse to https://mail.domain.com/OAB I am given the output:
403 - Forbidden: Access is denied.
You do not have permission to view this directory or page using the credentials that you supplied.

When I ctrl+right click the outlook icon on a domain joined client and select to test the settings, I get:

Autoconfiguration has started, this may take up to a minute
Autoconfiguration was unable to determine your settings! (this is displayed INSTANTLY after clicking test)

The Log output is as follows:

Attempting URL https://mail.domain.com/autodiscover/autodiscover.xml found through SCP
Autodiscover to https://mail.domain.com/autodiscover/autodiscover.xml starting
Autodiscover to https://mail.domain.com/autodiscover/autodiscover.xml FAILED (0X80072F0C)
Autodiscover to https://domain.com/autodiscover/autodiscover.xml starting
Autodiscover to https://domain.com/autodiscover/autodiscover.xml FAILED (0x800C8293)
Autodiscover to https://autodiscover.domain.com/autodiscover/autodiscover.xml starting
Autodiscover to https://autodiscover.domain.com/autodiscover/autodiscover.xml FAILED (0x800C8203)
Local autodiscover for domain.com starting
local autodiscover for domain.com FAILED (0x8004010F)
Redirect check to http://autodiscover.domain.com/autodiscover/autodiscover.xml starting
Redirect check to http://autodiscover.domain.com/autodiscover/autodiscover.xml FAILED (0x80072EE7)
Srv Record lookup for domain.com starting
Srv Record lookup for totalsolutionsgroup.biz FAILED (0x8004010F)

more info:

https://mail.domain.com/OWA - Works perfectly. certificate is shown, can do everything.

In outlook client, noone in the office has ever been able to use OOF, we get a message about the service being unavailable.

All of the WebServices have options for Basic and WindowsIntegrated authentication set to true

And don't even get me started on trying to get OA working! I'm not even slightly close. I have mstsc access to a pc not joined to domain and i'm getting nowhere with it at all.

If any of you guys can help me out i'd be a very happy bunny, i feel like i've wasted a ton of time trying to get this sorted out and I don't think i'm getting anywhere.

Cheers

David