Things to check ((Assuming you're already discarded connectivity issues: access to exchange, test port with telnet)):
- Test Autodiscover on the troubled host, here's an offline tool for that (read more here).
- DNS (Flush your DNS (ipconfig /flushdns, /registerdns).
- You say the machine is getting settings from GPOs, I'd be tempted to do a result and cross reference with another working machine... also check the OU this machine was added to (Not sure specifically how this would matter to you though, you're going to have to assess what settings the machine is supposed to be getting).
- There is no real good way (that I know) to be 100% that your Outlook client is installed properly. I'd also be tempted to repair the install, or even uninstall and re-install outlook.
Don't you love it when similarly (or identically) configured machines, that are supposed to work the same, somehow don't?... Well, the nice thing is that you have a known working configuration, and this box's issue just happens to be an anomaly. Remember to reboot a few times after forcing a gpupdate, if you're needing to fix GP settings, or repairing the software... or try a new user in case this user's profile is corrupt somehow.