If your developing EWS code against Exchange Online or possibly another large load balanced Hosted Exchange system you may find that a lot of the sample code you see on MSDN or other places that uses EWS Proxy code will always return 401 errors when you try to use it against Exchange Online (The Managed API isn't affected) eg a standard example is something like http://msdn.microsoft.com/en-us/library/bb408524%28v=EXCHG.140%29.aspx . What can cause this problem is the failure to process the exchangecookie in an appropriate way. There is description of what the exchangecookie is used for on http://blogs.msdn.com/b/exchangedev/archive/2011/07/20/client-access-server-affinity-and-network-load-balancing-considerations-for-programmatic-access-to-exchange-online.aspx . Although this says nothing about Authentication if the request object your using be its a SOAP proxy or HttpwebRequest doesn't have the cookiecontainer initialized (which by default they don't) before you submit
Pushing the Envelope in Messaging and Office 365 Development