SPNEGO with NTLM is required if you want to authenticate with a MS Dynamics NAV 2009. I'm using various authentication mechanismns from "org.apache.httpcomponents:httpclient:4.2.3". But SPNEGO with NTLM is not supported out of the box. Copiing HttpClient's NTLMScheme and making some changes has done the trick.

JCIFSEngine.java

import java.io.IOException;

import jcifs.ntlmssp.NtlmFlags;
import jcifs.ntlmssp.Type1Message;
import jcifs.ntlmssp.Type2Message;
import jcifs.ntlmssp.Type3Message;
import jcifs.util.Base64;

import org.apache.http.impl.auth.NTLMEngine;
import org.apache.http.impl.auth.NTLMEngineException;

/**
 * NTLM is not supported by HttpClient, but the link describes a way to do it and presents this class. 
 *  
 * http://hc.apache.org/httpcomponents-client-ga/ntlm.html
 */
public final class JCIFSEngine implements NTLMEngine {

  private static final int TYPE_1_FLAGS = 
      NtlmFlags.NTLMSSP_NEGOTIATE_56 | 
      NtlmFlags.NTLMSSP_NEGOTIATE_128 | 
      NtlmFlags.NTLMSSP_NEGOTIATE_NTLM2 | 
      NtlmFlags.NTLMSSP_NEGOTIATE_ALWAYS_SIGN | 
      NtlmFlags.NTLMSSP_REQUEST_TARGET;

  public String generateType1Msg(final String domain, final String workstation)
      throws NTLMEngineException {
    final Type1Message type1Message = new Type1Message(TYPE_1_FLAGS, domain, workstation);
    return Base64.encode(type1Message.toByteArray());
  }

  public String generateType3Msg(final String username, final String password,
      final String domain, final String workstation, final String challenge)
          throws NTLMEngineException {
    Type2Message type2Message;
    try {
      type2Message = new Type2Message(Base64.decode(challenge));
    } catch (final IOException exception) {
      throw new NTLMEngineException("Invalid NTLM type 2 message", exception);
    }
    final int type2Flags = type2Message.getFlags();
    final int type3Flags = type2Flags
        & (0xffffffff ^ (NtlmFlags.NTLMSSP_TARGET_TYPE_DOMAIN | NtlmFlags.NTLMSSP_TARGET_TYPE_SERVER));
    final Type3Message type3Message = new Type3Message(type2Message, password, domain,
        username, workstation, type3Flags);
    return Base64.encode(type3Message.toByteArray());
  }

}

SpNegoNTLMScheme.java

import org.apache.http.Header;
import org.apache.http.HttpRequest;
import org.apache.http.auth.AUTH;
import org.apache.http.auth.AuthenticationException;
import org.apache.http.auth.Credentials;
import org.apache.http.auth.InvalidCredentialsException;
import org.apache.http.auth.MalformedChallengeException;
import org.apache.http.auth.NTCredentials;
import org.apache.http.client.params.AuthPolicy;
import org.apache.http.impl.auth.AuthSchemeBase;
import org.apache.http.impl.auth.NTLMEngine;
import org.apache.http.impl.auth.NTLMScheme;
import org.apache.http.message.BufferedHeader;
import org.apache.http.util.CharArrayBuffer;


/**
 * Based on {@link NTLMScheme}
 * @author m.oberwasserlechner@mum-software.com
 *
 */
public class SpNegoNTLMScheme extends AuthSchemeBase {

  enum State {
    UNINITIATED,
    CHALLENGE_RECEIVED,
    MSG_TYPE1_GENERATED,
    MSG_TYPE2_RECEVIED,
    MSG_TYPE3_GENERATED,
    FAILED,
  }

  private final NTLMEngine engine;

  private State state;
  private String challenge;

  public SpNegoNTLMScheme(final NTLMEngine engine) {
    super();
    if (engine == null) {
      throw new IllegalArgumentException("NTLM engine may not be null");
    }
    this.engine = engine;
    this.state = State.UNINITIATED;
    this.challenge = null;
  }

  @Override
  public String getSchemeName() {
    return AuthPolicy.SPNEGO;
  }

  public String getParameter(String name) {
    // String parameters not supported
    return null;
  }

  public String getRealm() {
    // NTLM does not support the concept of an authentication realm
    return null;
  }

  public boolean isConnectionBased() {
    return true;
  }

  @Override
  protected void parseChallenge(
      final CharArrayBuffer buffer,
      int beginIndex, int endIndex) throws MalformedChallengeException {
    String challenge = buffer.substringTrimmed(beginIndex, endIndex);
    if (challenge.length() == 0) {
      if (this.state == State.UNINITIATED) {
        this.state = State.CHALLENGE_RECEIVED;
      } else {
        this.state = State.FAILED;
      }
      this.challenge = null;
    } else {
      this.state = State.MSG_TYPE2_RECEVIED;
      this.challenge = challenge;
    }
  }

  public Header authenticate(final Credentials credentials, final HttpRequest request) throws AuthenticationException {
    NTCredentials ntcredentials = null;
    try {
      ntcredentials = (NTCredentials) credentials;
    } catch (ClassCastException e) {
      throw new InvalidCredentialsException(
          "Credentials cannot be used for NTLM authentication: "
              + credentials.getClass().getName());
    }

    String response = null;
    if (this.state == State.CHALLENGE_RECEIVED || this.state == State.FAILED) {
      response = this.engine.generateType1Msg(
          ntcredentials.getDomain(),
          ntcredentials.getWorkstation());
      this.state = State.MSG_TYPE1_GENERATED;
    } else if (this.state == State.MSG_TYPE2_RECEVIED) {
      response = this.engine.generateType3Msg(
          ntcredentials.getUserName(),
          ntcredentials.getPassword(),
          ntcredentials.getDomain(),
          ntcredentials.getWorkstation(),
          this.challenge);
      this.state = State.MSG_TYPE3_GENERATED;
    } else {
      throw new AuthenticationException("Unexpected state: " + this.state);
    }

    CharArrayBuffer buffer = new CharArrayBuffer(32);
    if (isProxy()) {
      buffer.append(AUTH.PROXY_AUTH_RESP);
    } else {
      buffer.append(AUTH.WWW_AUTH_RESP);
    }
    buffer.append(": ");
    buffer.append(getSchemeName().toUpperCase());
    buffer.append(" ");
    buffer.append(response);
    return new BufferedHeader(buffer);
  }

  public boolean isComplete() {
    return this.state == State.MSG_TYPE3_GENERATED || this.state == State.FAILED;
  }

}

SpNegoNTLMSchemeFactory.java

import org.apache.http.auth.AuthScheme;
import org.apache.http.impl.auth.NTLMSchemeFactory;
import org.apache.http.params.HttpParams;

public class SpNegoNTLMSchemeFactory extends NTLMSchemeFactory {

  public AuthScheme newInstance(final HttpParams params) {
    return new SpNegoNTLMScheme(new JCIFSEngine());
  }

}

This is the only Java implementation of Negotiate NTLM that I've found. Thank you a lot!