AFAIK, Error Code -3259 is the result of EWS's "Outlook Exchange Auto Configure" not working as intended or at all. There are likely issues between the server and the client, but you guy knew that already! If you're positive all of your entered settings are correct, there's one more item to check that's been a bug in Outlook for a couple of years. I'm not clear on whether "autodiscover" on your end is disabled or just not functioning as intended, but read on...
On a related matter, there were layout bugs in Excel 2008 that I found that existed for some time until a bug fix was finally issued - they called the bug fix "Excel 2011" and it wasn't a free bug fix.

My point here is that I know that there was an autodiscovery bug in Outlook 14.1.3 when connecting to Exchange 2007, and I doubt it's been fixed given MS's sloth-like history for non-security bug fixes in Mac Office apps.
The workaround: Open up the Mac's Date & Time System Preference. Open up Outlook and open up it's Preferences Pane (see the image). Change the Mac's Time Zone (uncheck "Set date and time automatically") to the
same Default time zone as that found in Outlook - ideally, to the same time zone you're in at the time. I had to deal with this some 3 years ago.
Once the time zone in the Mac's System Preferences matched that in Outlook, autodiscover was able to pull the settings correctly for our mailboxes and connect to download mail/calendars/contacts and access our GAL.