Some servers doesn't send a authentication challange response (401), so the authentication header is not sent in the next request attempt (default behaviour in the Apache Commons Http Client).
To send always the authentication header, the preemptive authentication must be enabled. In the case of Apache Commons Http Client, the AuthCache must be present in the HttpContext. I attached a patch that solves this.