Hrm...
If setting up any profile on this machine has the same problem, and re-installing Outlook does not help.
Would begin to think this problem is PC related not Outlook related.
Assuming all DNS and Network Settings Are Correct, User Accounts have appropriate permissions both on the network and local PC...
Personally I would backup anything I could.
De-join the PC from the Network.
Remove the computer from AD
Re-Add the computer and see if it fixes the issue.
If it doesnt, I would then try repairing the OS and most likely Rebuild.