I've been using Outlook 2001 on OS X since 10.0.4 in August 2001. I'm now up to 10.1.5 and still waiting for thy software gods in Redmond to release an OS X version. The classic version works OK but has the glitches that I still see when booted into OS 9.
(delete key doesn't work until I delete with X toolbar button, sometimes can't copy and paste between Classic apps and Carbon/Cocoa apps, etc)
If you can't connect to the Exchange server, use Mac TCP Watcher (OS 8.x,9.x) of use the Network Info utility (OS X) to ping the Exchange servers address. If you can ping it, then you are not setting up your Outlook properly.
-John