Index corrupted

Some of our users are experiencing an issue when trying to send emails. Index corrupted - will be rebuilt automatically when the database is closed or server is restarted. Updall, fixup does not fix this problem. I have replaced designs of databases, created new replica’s of the databases, but we still have this problem for a lot of users. They are however able to log into iNotes and this works fine. Please help

Subject: Index

Could be an index in your names.nsfTry to do a fixup or updall -R on names.nsf

Subject: index

We have carried out fixups, updall and compacts to try and resolve this issue. We did find that the problem was for users that had there recipient name lookup set to exhaustivly look at all address books, once this was changed they were able to send mail OK. But we did notice that after that if a user was sending an email to a personal group, then they got the same error and only by selecting the users from outside there pernames did it send OK?