Не уверен, как вы передаете Credentials через свойства веб-сервиса. Есть 2 пути...
1. Неправильный (как вы, возможно, и делаете):
User (System.Net.NetworkCredential). Определить - User.UserName, User.Password.
NAVService.Credentials = User
2. Правильный, с использованием CredentialCache:
Пример приведен
здесь
WebServicesUseNTLMAuthentication в CustomerSettings должно быть true.