Turns out they were trying to bind to ldap://domain_name, where domain name was programmatically derived from System.Environment.UserDomainName; in some cases said property would return, instead of the logged on user's domain name, the local computer name. Thing is, you would expect a property in System.Environment to return the value of an evironment variable, presumably USERDOMAIN, which we verified contained the appropriate value.

Digging around in the documentation didn't help, so I turned to ye olde Reflector:

Note the function call in bold; a quick look in MSDN revealed the following information:

BOOL LookupAccountName(
  LPCTSTR lpSystemName,
  LPCTSTR lpAccountName,
  PSID Sid,
  LPDWORD cbSid,
  LPTSTR ReferencedDomainName,
  LPDWORD cchReferencedDomainName,
  PSID_NAME_USE peUse
);

Note the part marked in red: Environment.UserDomainName does indeed pass null for lpSystemName, so if the machine contains a local user by the same name as the domain user, the local machine name will be returned instead of the domain. This behavior is apparently by design, although I can't figure out how that makes any sense what-so-ever.

There are two easy ways to avoid this issue:

string userDomain = Environment.GetEnvironmentVariable( "USERDOMAIN" );
string userDomain = System.Security.Principal.WindowsIdentity.GetCurrent().Name.Split( @'\' )[ 0 ];

Have fun.