There was said:
"The CrmService Web service provides a set of methods used to perform the most common operations on system and custom entities. These operations can also be performed by using the Execute method and the corresponding message. However, the methods will perform faster so they should be used whenever possible."
So service.Update is a winner.