This is a common experience when the owner of the domain has not configured AutoDiscover. Normally, a CName would be created pointing to the Exchange service for AutoDiscover redirection.

Start by contacting your exchange service provider and ask them what the redirect address is.

This is a requirement for Exchange 2010 and below is some additional reading:
http://technet.microsoft.com/en-us/l.../bb124251.aspx

Best Regards,