Yes, it can take a while. However, you may be able to speed things up. The best practice is to store the EWS web service URL set on the service object and use it next time instead of doing AutoDiscover again. SCP AutoDiscover should be avoided unless you need to use it. Also keep in mind that you should be only doing AutoDiscover if you really need to – but then always do it if you need to.
If you're code is going against Exchange Online or have a custom domain then the URL is probably not going to change and you may get away with not doing AutoDiscover in the first place, However, you should have a fallback of redoing AutoDiscover if it does.
On the ExchangeService object there is a property called EnableScpLookup. By default, it is set to true. There are two types of AutoDiscover used by the EWS Managed API. The first is the SCP AutoDiscover process, which will run if EnableScpLookup is set to true. SCP AutoDiscover will ping AD for information on possible servers to discover against then will do POSTs to try to get discovery information. If your server is in-network with your client application, then the SCP AutoDiscover process should be able to find the EWS web service URL for the mailbox. If SCP AutoDiscover fails then the EWS Managed API will then try POX AutoDiscover, which uses patterns based-upon the SMTP address to build URLS to do POSTs with in order to try to find the EWS web service URL. POX is used for out of network AutoDiscover – so it should be used with Exchange Online or when the client application is otherwise not in-network with the Exchange server. If EnableScpLookup is set to 'false' then the SCP AutoDiscover process is skipped and the POX AutoDiscovery process is run.
So, why is this important? Well, AutoDiscover processes are expensive. So, only do it when you need to, but do it when its needed. If you are not caching the AutoDiscover results, then you are waiting time by doing it when it's not needed. If you do SCP AutoDiscover when going against Exchange Online, then you are wasting time. As a real world example I've seen, if you AutoDiscover go against Exchange Online with EnableScpLookup set to true and the call takes 20 seconds to finish then around 18 seconds may have been taken up by the SCP AutoDiscover process doing LDAP calls against AD and the final two seconds were for POX AutoDiscover. If the server had been in-network, then it would have completed far faster. However, if EnableScpLookup was set to false then the AutoDisocvery call would have finished far faster since it would only have had to do POX Autodiscover. So, be sure to set EnableScpLookup correctly for every ExchangeService object you instance.
Here are some links for reference:
Autodiscover for Exchange
How to: Generate a list of Autodiscover endpoints