After a lot of days spending on troubleshooting the issue with Office 365 accounts prompting for credentials pop-up again and again for Outlook 2013 users. We finally got the fix which resolved our issue.

https://community.office365.com/en-us/f/172/t/353502

We have on-premises exchange server and also we have Office 365 mailbox. After creating new registry entry 

ExcludeScpLookup=dword:1 

in HKEY_CURRENT_USER\Software\Microsoft\Office\15.0\Outlook\AutoDiscover 

that resolved our issue. 

Now just wondering, how to do a permanent fix. From the support and forums, I can perceive that removing SCP entry from AD would do the fix. However, I am not sure what would be the impact of this change on local on-premises exchange server.

Please help

Are you in hybrid mode?  If you are, then the SCP should point to the local Exchange server, which will redirect Autodiscover to Office 365 for cloud mailboxes.  If you're not in hybrid mode, you probably should be.

Hi,

Please do the following changes to narrow down the issue:

1. What's your Exchange environment? Hybrid deployment?

2. Confirm whether the credential promped issue happens to all Exchange On-premises users or all Exchange Online users.

3. Please make sure the opened shared mailbox is also moved to the same location as the primary mailbox hosted (on-premises or Online).

4. Please remove the shared mailbox from Outlook and confirm whether the issue persists.

5. If you are using Hybrid environment, please configure the Autodiscover public DNS records for your existing SMTP domains to point to an on-premises Exchange 2013 Client Access server. 

6. Check the Connection Status (press and hold Ctrl, and then right-click the Outlook icon in the notification area, click Connection Status) in Outlook client side and collect the Server name, status, protocol, Authentication, and Type information when the issue occurs.

Regards,