It depends on the configuration of you exchange server. Try using the different usernames who can be configured on exchange servers:
ExchangeService service = new ExchangeService();
ExchangeCredentials credentials = new WebCredentials("user@domain.com","pass");
or
ExchangeCredentials credentials = new WebCredentials(Username,Password, domain);
or
ExchangeCredentials credentials = new WebCredentials("user", "pwd");
service.setCredentials(credentials);
In my case, the one who works is the Username,Password,Domain method.