I would not go through each record in the scenario you describe. Web services are fine but you could as easily use them for bulk updates.
From the top of my head, something like this would work a little better:
- Get a 'diff' containing all the changes in the master database. This could be done before the synchronisation starts and only has to be done once per day.
- Send a full list of contacts from the client to the server. With a list that big it does not really matter how it is send but if you don't like SOAP web services think about JSON. I would go with web-services for convenience. Again, the list of contacts could be prepared in advance.
- Create a list of records which need to be update by comparing the 'diff'with the list from the client.
- Get all the updated details in one go (if you use MS SQL you could do that with XML, other SQL services offer different paths)
- Send the details to the client
The same mechanism could be used for updating one record only, you just need to use different list (containing 1 ID) in the p.2