Hi,
What is the value set on the AutoDiscoverServiceInternalUri for Exchange 2010 and Exchange 2016?
Let's suppose it is set to autodiscover.domain.com for both Exchange 2010 and 2016, does the DNS record for autodiscover.domain.com is pointing to the Load balancer VIP? If so, please check if the Exchange 2010 IP is still added in the VIP in load balancer. Try removing it if its added.
You can also add host file entry on the client machine for autodiscover.domain.com to point to Exchange 2016 to make sure if the delay is actually on the Exchange server or reaching the server.
Also, can you let us know if this happens for Exchange 2016 mailbox or Office 365 mailbox? For all users or specific users? or recently migrated users to office 365?