Last time I had this error was because my Veritas user didn't have rights to certain mailboxes. Easy to check... Login as the Veritas user to the server. Then create the Outlook profile for this user. If it gives you a permission error... There's your answer.
