Journal enabled seems to fill queue "Messages awaiting directory lookup"

We have a problem when enabling the Journal option on the Exchange mailstore.
After serveral minutes messages seem to add up in the queue "Messages awaiting directory lookup".
This is a problem with many causes and many fixes.
First let me tell you what we have done / found and how our Exchange environment is setup:

Journaling is set on the Private store. It uses a journal@ourcompany.com address to copy the messages to. This journal mailbox is on a second store specifically for journalling (as stated in serveral docs)
Basically we only clicked the option Enable Journaling and entered the mailbox right there. Nothing else has been done, so I have no idea if it is doing envelope/bcc/etc.

When setting the logging level to debug (level 7 by changing something in the registry) we found a bunch of errors telling us that it is the Categorizer which seems to have trouble.

But what is weird here: The messages awaiting directory lookup are in the queue of our Frontend server.
See attached picture of our setup. (EDIT: It is not weird as all messages in this queue are messages to outside addresses. So it looks like it cannot resolve DNS queries? As a nslookup works fine though and there is no trouble when setting journalling disabled)

On both Exchange Servers in the System Manager, the setting "Allow enheritable permissions from the parent..." is checked (on the tab Security > Advanced)

Here are some logged events with Journalling set to disabled (hence no mail goes out anymore)

This is an SMTP protocol log for virtual server ID 1, connection #4080. The client at "172.20.0.22" sent a "xexch50" command, and the SMTP server responded with "504 Need to authenticate first  ". The full command sent was "xexch50 2912 2".  This will probably cause the connection to fail.

The transport configuration type 1 for the directory entry with DN or GUID CN=MICROSOFT MTA,CN=CAP-EXCHFE02,CN=SERVERS,CN=FIRST ADMINISTRATIVE GROUP,CN=ADMINISTRATIVE GROUPS,CN=VEENMAN,CN=MICROSOFT EXCHANGE,CN=SERVICES,CN=CONFIGURATION,DC=VEENMAN,DC=INTERN is not one of the supported values. Reconfigure the transport configuration type in the identified directory entry. [BASE IL OPERATOR 23 217] (8)

With journalling on (a few seconds later) events like 6006, 6008 and 9003 are shown.

Categorizer encountered a hard error while processing a message.  The function 'CICategorizerMailMsgsIMP::ReBindMailMsg' called 'pEntry->pIMailMsgProperties->RebindAfterFork' which returned error code '0xc004012f' (). ( f:\tisp2\transmt\src\phatq\cat\src\icatmailmsgs.cpp@746 )

Categorizer is temporarily unable to process a message.  While processing user 'smtp:someone@ourcompany.com', the function 'CPhatCat::HrHandleNewMessage' called 'ReBindMailMsg' which returned error code '0xc0040559' (The categorizer encountered an error.  The operation will be restarted.
). ( f:\tisp2\transmt\src\cat\sinks\phatcat\cptbif.cpp@2546 )

Categorizer is temporarily unable to process a message.  While processing user 'smtp:someone@ourcompany.com', the function 'CPhatCat::HrGetBifurcatedMessage' called 'HrHandleNewMessage' which returned error code '0xc0040559' (The categorizer encountered an error.  The operation will be restarted.
). ( f:\tisp2\transmt\src\cat\sinks\phatcat\cptbif.cpp@826 )

Categorizer is temporarily unable to process a message.  While processing user 'smtp:someone@ourcompany.com', the function 'CPhatCat::HrResolveJournalRecipient' called 'HrGetBifurcatedMessage' which returned error code '0xc0040559' (The categorizer encountered an error.  The operation will be restarted.
). ( f:\tisp2\transmt\src\cat\sinks\phatcat\cptmaildrop.cpp@1790 )

Categorizer is temporarily unable to process a message.  While processing user 'smtp:someone@ourcompany.com', the function 'CPhatCat::HrJournalRecipient' called 'HrResolveJournalRecipient' which returned error code '0xc0040559' (The categorizer encountered an error.  The operation will be restarted.
). ( f:\tisp2\transmt\src\cat\sinks\phatcat\cptmaildrop.cpp@1162 )

Categorizer is temporarily unable to process a message.  While processing user 'smtp:someone@ourcompany.com', the function 'CPhatCat::CompleteSender' called 'HrJournalRecipient' which returned error code '0xc0040559' (The categorizer encountered an error.  The operation will be restarted.
). ( f:\tisp2\transmt\src\cat\sinks\phatcat\cptcomplete.cpp@233 )



mailroute.png