A good place to start understanding how the Mobility Service works is here: http://technet.microsoft.com/en-us/library/hh690030.aspx. Most of the steps are already provided in Technet but I find that many of the key essential must-do's are scattered in various pages rather than being consolidated in a single location.  Hence, this article serves as a companion to the Technet documentation and is intended for anyone who is encountering difficulty in successfully getting the Mobility service to work. It will also be useful in case I ever need to deploy the Mobility Service again in a different environment and do not wish to spend time to troubleshoot the commonly encountered issues. The diagram below reproduced from Technet is very helpful to understand the how the mobility service works:

During Automatic Discovery, mobile devices will first use DNS lookup to the internal DNS record lyncdiscoverinternal.<internal domain>. If not found, it means that the client is on an external network and will then lookup the external DNS record lyncdiscover.<sipdomain>. A mobile device that is internal to the network connects to the internal Autodiscover Service URL, and a mobile device that is external to the network connects to the external Autodiscover Service URL. For split-brain DNS environment, the internal autodiscover DNS record should exist in the internal DNS and not in the external public DNS. Vice versa, the external autodiscover DNS record should exist in the external public DNS and not in the internal DNS.

With the release of Exchange 2013 CU1, we can finally deploy the Unified Contact Store (UCS) into an existing Exchange2010 SP3 environment. This is because Exchange2013 is required for UCS and the GTM version of Exchange2013 did not support coexistence with previous versions of Exchange. To recap, UCS enables users to store all contact information in Exchange 2013 so that the information is available globally across Lync, Exchange, Outlook, and Outlook Web Access. Without UCS, Lync2013 clients cannot change or upload their photos. Below is the UCS architecture diagram for reference:

Deploying Exchange2013 CU1 itself is beyond the scope of this article and the steps are provided in Technet. For existing Exchange2010 environments as in the case of this lab setup, upgrading to Exchange2010 SP3 is required which also performs the prepare AD schema, thereby eliminating the need to run setup.exe /PrepareSchema using Exchange2013. After deploying Exchange2013 we also need to run the post-install steps as described in here. Most notably would be the need to assign a CA issued certificate for the CAS role as Exchange2013, like it's predecessors, by default uses a self-signed cert which Lync2013 will not recognize. Once the prerequisites are done, enabling unified contact store in Lync Server 2013 does not require any topology settings. All that's needed is that the Unified contact store policy is enabled (default is enabled), user's mailboxes have been migrated to Exchange2013, and user log in with using the Lync 2013 rich client at least once.