Unable to deploy Dynamics 365 App for outlook: "Issue when adding to outlook".

While deploying app for outlook from Dynamics CE you will see an error in red in front of users mailbox "Issue when adding to outlook". If you click more details, you see the message "Invalid data source operation".

If you navigate to Manage addins from a users mailbox, you will see the following error:

"Could not locate Client Access Virtual Directory Object with InternalURl stamped for ECP, service."

Note : For an Office addin to be deployed to a user's mailbox in Exchange, "AppsForOfficeEnabled" should be true. You can the following command to check the configuration settings through Exchange Management Shell (EMS).

Get-OrganizationConfig | Format-List AppsForOfficeEnabled

This is due to the Discovery search from Exchange Admin Center (EAC). Whenever discovery search is performed for the first time using EAC in Exchange 2013, it will check for the following 6 internal URLs in the background and it will cache it locally

Found URL: https://e15-cas.contoso.com/owa
Found URL: https://e15-cas.contoso.com/ecp
Found URL: https://e15-cas.contoso.com/EWS/Exchange.asmx
Found URL: https://e15-cas.contoso.com/Microsoft-Server-ActiveSync
Found URL: https://e15-cas.contoso.com/OAB
Found URL: https://e15-cas.contoso.com/mapi
[GlobalServiceUrls.DiscoverUrlsIfNeeded] Successfully found all needed VDirs

Make sure all the required virtual directories are present and internal URLs are published on those virtual directories.

For more details on how to configure Exchange virtual directories, see the folllowing URL:
https://docs.microsoft.com/en-us/Exchange/plan-and-deploy/post-installation-tasks/configure-mail-flow-and-client-access?view=exchserver-2019#step-4-configure-external-urls