I don't think the problem is exactly the same for the original post, but I would recommend reading
this post about improving the performance of the WebServiceClient and any web service client for that matter. If the DataRepository.ContactsProvider.GetAll() is the first time the service gets called .net generates a large amount of serialization information for the first instantiation, thereafter the speed increases.