I suggest you perform a dtrace of the archive tasjk fior one mailbox and that will tell you message by message why the item is not archived. To do the Dtrace:

Are these emails all "original"? As in never been archived before, subsequently restored etc, as that can have a bearing.

Worth doing what Percy says, it will at least tell you the eligibilty testing.

Thank you for the reply. I'll trace it using dtrace as mentioned.

I'll let you know the result.

Andy

Also is this from scheduled archiving or on Run Nows?
It could be the Messages Per Pass which is set by default
So when the arching schedule first kicks off, it pushes every enabled user in to the exchange archiving tasks A5 queue, the task then goes through (usually 5 at a time by default) and connects to each mailbox and finds messages to archive, moved shortcuts and such

To keep things moving there is a Messages per pass setting, so by default it's set to 1000 email, after archiving 1000 email it then moves on to the next mailbox and so on and so forth until the A5 queue is cleared or until the archiving schedule ends, if it is clear and time is left in the schedule, it will requeue users who still had items to archive, and it will keep requesting users until its all complete or the Schedule runs out

So it could be something like schedule is too short, messages per pass too high, too many users on the exchange server, or as suggested it could be that items not being archived were previously restored in which case EV will not rearchive them until certain time has passed

Other than that could be something like the wrong message class, read vs unread, do not archive has been set on an item etc, but only the DTrace will tell you that for definite

This is a test phase. The schedule is stopped and we are archiving manually: "RUN NOW" in normal mode. At this time, we are archiving 3 small mailboxes, that's all. In this case, the queue should be able to process all items. But for instance, we are unsure if actually archived items are from a previous archiving run. In between the customer did changes to the configuration... It's quite possibe, that items do not archive "anymore"... to check this out, we are attaching another mailbox and try it with the new one...

The dtrace has listed all allready archived items (Shortcutcreation), but failed items are not listed in the (verbose) log. There could be another issue (error message) in the log, but i didn't find it until now.

Andy

http://www.symantec.com/docs/HOWTO42224

Does this technote assist with understanding the logic?  You can use tools like Outlook Spy and MFCMAPI to view message MAPI attributes that are mentioned in the article.  

If you see in the dtrace that the item is ineligable for archiving this is usually the reason why.