There's a bunch of utilities that may help you remove the message. Consult support before you try anything on your own. As you stated the real issue is whether the message you remove is required for retention. If you can determine the MsgId in the healthcheck tool run a select query on the Message table in SQL. At least you'll be able to see the message date and subject. Here's an example:

select * from message where md5hashkey = -9184823622729860681

Using this information you can try to restore the message from backup.

There's also the possibility the message is in the BadDir directory under the MsgCenter folder or it may be quarantined by AntiVirus software.

Hope this helps.

There are more than 140 messages that it would be needed to remove. That is quite a lot? It there any other solution to this problem with the indexes?

If the volumes for the affected month are closed (that is, they're all .emx files) then Dispose Monthly Data using the EX Admin program. You can then restore the volumes from Lost and Found.

The Dispose Monthly Data step deletes the ISYS full text indexes and the SQL data for all emails associated with the volumes for that month. The restoration from Lost and Found will recreate the SQL indexes and rebuild the indexes from scratch.

Is there any log that is created after this restoration takes place? We would like to identify the messages that causes this problem and possibly add an rule to EmailXtender not to index them in the future.

There is no log. It would be very diffcult to create a rule to block these emails.
Is it possible the emails were quarantined by AV software on the EX machine? I've seen AntiVirus cause problems like this more than once in the past.

I just analyzed the 200606_000\INDEXERR.LOG file for the June 2006.
Inside, there are exactly 63 lines with the content like this:

CRITICAL ERROR: NON-UNIQ MsgId: 45DDE42CD773E9315432B68E, Doc: 45DDE42CD773E9315432B68E.access

When I look in the the health check, 63 is the exact amount of missing messages for that month.

Can anyone give me a hint what to do here?
How to avoid these critical errors?
And why do they happen?

Never seen that error before. Is there a message in the OTG event log?
You may see a message similar to the ones pasted below.

Symptom: Index not available for your exclusive use, or insufficient network rights
Symptom: indexing Problem
Symptom: Index Process Error mm/dd/yy hh:mm:ss ERROR: Index not available for your exclusive use, or insufficient network rights to index or permits.: (A 033 -1 34)
Symptom: Index Process Error mm/dd/yy hh:mm:ss Error: Corrupt index E:\Program Files\OTG\EmailXtender\EmailVault_Index\IndexDir\EmailVault_Index_Archive\20 0404\000. Need to reindex the monthly data.
Cause: Backup of Emailxtender index directory is causing a conflict or
Anti-virus software is causing conflict.
Fix: Exclude all EmailXtender directories from being scanned by the Anti-virus application.
Use the Exsuspend.exe utility to idle EmailXtender services before running Backups.

There is no anti-virus running on the server.
For this particular month there are more than 13000 messages indexed, and 63 of them have this problem.