No firewall, no security software.
It is something to do with the IIS configuration though. I'll look at the config of IIS and see if I can spot the problem and correct it.
Non the less here is a packet capture of lsclient at work which clearly shows IIS's involvement:
GET /normal?comp=P3-343KG-01&domain=AD&userdomain=AD&user=XXXX&site=PG&ip=ME.XXX.XXX.XXX HTTP/1.1
Host: MYSERVER:9524
Accept: text/html, */*
Accept-Encoding: identity
User-Agent: Mozilla/3.0 (compatible; Indy Library)
HTTP/1.1 401 UnauthorizedContent-Length: 1656
Content-Type: text/html
Server: Microsoft-IIS/6.0
WWW-Authenticate: Negotiate
WWW-Authenticate: NTLM
X-Powered-By: ASP.NET
Date: Thu, 30 Apr 2009 15:29:25 GMT
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<HTML><HEAD><TITLE>You are not authorized to view this page</TITLE><META HTTP-EQUIV="Content-Type" Content="text/html; charset=Windows-1252">
<STYLE type="text/css">
BODY { font: 8pt/12pt verdana }
H1 { font: 13pt/15pt verdana }
H2 { font: 8pt/12pt verdana }
A:link { color: red }
A:visited { color: maroon }
</STYLE>
</HEAD><BODY><TABLE width=500 border=0 cellspacing=10><TR><TD>
<h1>You are not authorized to view this page</h1>
You do not have permission to view this directory or page using the credentials that you supplied because your Web browser is sending a WWW-Authenticate header field that the Web server is not configured to accept.<hr>
<p>Please try the following:</p>
<ul>
<li>Contact the Web site administrator if you believe you should be able to view this directory or page.</li>
<li>Click the <a href="javascript:location.reload()">Refresh</a> button to try again with different credentials.</li>
</ul>
<h2>HTTP Error 401.2 - Unauthorized: Access is denied due to server configuration.<br>Internet Information Services (IIS)</h2><hr>
<p>Technical Information (for support personnel)</p>
<ul>
<li>Go to <a href="http://go.microsoft.com/fwlink/?linkid=8180">Microsoft Product Support Services</a> and perform a title search for the words <b>HTTP</b> and <b>401</b>.</li>
<li>Open <b>IIS Help</b>, which is accessible in IIS Manager (inetmgr),
and search for topics titled <b>About Security</b>, <b>Authentication</b>, and <b>About Custom Error Messages</b>.</li>
</ul>
</TD></TR></TABLE></BODY></HTML>
Kevin