Cannot enable UM for users

You cannot enable UM (Unified messaging) feature for users and get following errors.

Enable-UMMailbox -Identity <> -UMMailboxPolicy <> -Extensions <> -PinExpired:$true -SipResourceIdentifier <>

Exception:
Mailbox <> couldn't be initialized for Unified Messaging: There was an error accessing the mailbox using EWS. The requested operation failed with ResponseCode "ErrorInternalServerError". Details : An internal server error occurred. The operation failed.
+ CategoryInfo          : NotSpecified: (:) [Enable-UMMailbox], RecipientTaskException

Additionally you get following error while accessing the affected user's mailbox through OWA.

A problem occurred while you were trying to use your mailbox.
X-ClientId: <>
X-OWA-Error: SDServerErr;Microsoft.Exchange.Data.Storage.StoragePermanentException
X-OWA-Version: <>
X-FEServer: <>
X-BEServer: <>
Date: <>

This happens due to corruption in the Search of user's mailbox so we need to follow below steps to resolve it.

>Need to configure affected user’s Outlook profile in ONLINE mode.
>Run the MFCMAPI Tool and navigate to Session->logon.
>Select affected user's ONLINE profile.
>Right Click on the user and click on Open Store.
>Expand Root Mailbox->Finder.
>Permanently delete all folders starting with string Search*.
>Log Out from MFCMAPI.

Note:- Deleting search folders will remove all search queries from user's mailbox.