Для Оперы, на старом (закрытом ныне) форуме для пересоздания индекса почты советовали удалить (переименовать, переместить) папку mail\lexicon. Опера при запуске перезапускала создания индекса. Сам никогда эту операцию не проделывал. У меня почтовый ящик в Опере настроен на IMAP, а там это несколько сложнее... Пришлось исхитрятся по другому.

т.к. Opera Mail - это "огрызок" от Оперы, то можно попробовать "трюк" с папкой lexicon и на ней.