This is because the HTTP Negotiate authentication method is used:
"NTLM and Negotiate (RFC-4559) is most commonly used on Microsoft IIS web servers. NTLM can be used exclusively, but modern servers typically use Negotiate to select which scheme will be used. The result is usually NTLM'
Microsoft explains it e.g. here (see Figure 1)
If you Google for http request negotiation www-authenticate you'll find more info.
As an illustration, this is the HTTP that I see if SOAPUI makes an authenticated connection to Exchange web services:
1> >> "POST /ews/exchange.asmx HTTP/1.1[\r][\n]"
>> "Accept-Encoding: gzip,deflate[\r][\n]"
>> "SOAPAction: "http://schemas.microsoft.com/exchange/services/2006/messages/ResolveNames"[\r][\n]"
>> "Content-Type: text/xml; charset=utf-8[\r][\n]"
>> "Content-Length: 548[\r][\n]"
>> "Host: webmail.ttbv.nl[\r][\n]"
>> "Connection: Keep-Alive[\r][\n]"
>> "User-Agent: Apache-HttpClient/4.1.1 (java 1.5)[\r][\n]"
>> "[\r][\n]"
>> "<soapenv:Envelope [\n]"
[snip]
>> "</soapenv:Envelope>[\n]"
>> "[\n]"
1< << "HTTP/1.1 401 Unauthorized[\r][\n]"
<< "Cache-Control: private[\r][\n]"
<< "Server: Microsoft-IIS/7.5[\r][\n]"
<< "X-AspNet-Version: 2.0.50727[\r][\n]"
<< "Set-Cookie: exchangecookie=a29f10ca2a6d484ea276737e87d8e733; expires=Wed, 13-Nov-2013 10:47:33 GMT; path=/; HttpOnly[\r][\n]"
<< "WWW-Authenticate: Negotiate[\r][\n]"
<< "WWW-Authenticate: NTLM[\r][\n]"
<< "X-Powered-By: ASP.NET[\r][\n]"
<< "Date: Tue, 13 Nov 2012 10:47:33 GMT[\r][\n]"
<< "Content-Length: 0[\r][\n]"
<< "[\r][\n]"
2> >> "POST /ews/exchange.asmx HTTP/1.1[\r][\n]"
>> "Accept-Encoding: gzip,deflate[\r][\n]"
>> "SOAPAction: "http://schemas.microsoft.com/exchange/services/2006/messages/ResolveNames"[\r][\n]"
>> "Content-Type: text/xml; charset=utf-8[\r][\n]"
>> "Content-Length: 548[\r][\n]"
>> "Host: webmail.ttbv.nl[\r][\n]"
>> "Connection: Keep-Alive[\r][\n]"
>> "User-Agent: Apache-HttpClient/4.1.1 (java 1.5)[\r][\n]"
>> "Cookie: exchangecookie=a29f10ca2a6d484ea276737e87d8e733[\r][\n]"
>> "Cookie2: $Version=1[\r][\n]"
>> "Authorization: NTLM TlRMTVNTUAAB[snip]QgBWAA==[\r][\n]"
>> "[\r][\n]"
>> "<soapenv:Envelope [\n]"
[snip]
>> "</soapenv:Envelope>[\n]"
>> "[\n]"
2< << "HTTP/1.1 401 Unauthorized[\r][\n]"
<< "Server: Microsoft-IIS/7.5[\r][\n]"
<< "WWW-Authenticate: NTLM TlRMTVNTU[snip]AACAAAAFAAAAA==[\r][\n]"
<< "WWW-Authenticate: Negotiate[\r][\n]"
<< "X-Powered-By: ASP.NET[\r][\n]"
<< "Date: Tue, 13 Nov 2012 10:47:33 GMT[\r][\n]"
<< "Content-Length: 0[\r][\n]"
<< "[\r][\n]"
3> >> "POST /ews/exchange.asmx HTTP/1.1[\r][\n]"
>> "Accept-Encoding: gzip,deflate[\r][\n]"
>> "SOAPAction: "http://schemas.microsoft.com/exchange/services/2006/messages/ResolveNames"[\r][\n]"
>> "Content-Type: text/xml; charset=utf-8[\r][\n]"
>> "Content-Length: 548[\r][\n]"
>> "Host: webmail.ttbv.nl[\r][\n]"
>> "Connection: Keep-Alive[\r][\n]"
>> "User-Agent: Apache-HttpClient/4.1.1 (java 1.5)[\r][\n]"
>> "Cookie: exchangecookie=a29f10ca2a6d484ea276737e87d8e733[\r][\n]"
>> "Cookie2: $Version=1[\r][\n]"
>> "Authorization: NTLM TlRMTVNT[snip]AVABUADcANAA=[\r][\n]"
>> "[\r][\n]"
>> "<soapenv:Envelope [\n]"
[snip]
>> "</soapenv:Envelope>[\n]"
>> "[\n]"
3< << "HTTP/1.1 200 OK[\r][\n]"
<< "Cache-Control: private[\r][\n]"
<< "Transfer-Encoding: chunked[\r][\n]"
<< "Content-Type: text/xml; charset=utf-8[\r][\n]"
<< "Server: Microsoft-IIS/7.5[\r][\n]"
<< "X-EwsPerformanceData: RpcC=2;RpcL=0;LdapC=1;LdapL=0;[\r][\n]"
<< "X-AspNet-Version: 2.0.50727[\r][\n]"
<< "Persistent-Auth: true[\r][\n]"
<< "X-Powered-By: ASP.NET[\r][\n]"
<< "Date: Tue, 13 Nov 2012 10:47:33 GMT[\r][\n]"
<< "[\r][\n]"
<< "877[\r][\n]"
<< "<?xml version="1.0" encoding="utf-8"?><s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/">
[snip]
<< "</s:Envelope>"
<< "[\r][\n]"
<< "0[\r][\n]"
<< "[\r][\n]"
In the first received HTTP block the server tells me what protocols I can use.
So the second request is not, as you write if authentication fails, it is by design; hence no username and password have to be sent with the first request.