You might want to take a look at this thread:
Yet Another Local Failure Notice and add the logs requested in that here. That problem was not reproducible in Outlook 2007 and, of course, it may not be the same problem but that was
fixed in 6.0.4. Is there any chance you can upgrade to the most recent Zimbra 6.0.5 and Outlook Connector?