Q:

Call webservice with NTLM authentication

Is it possible calling a webservice using NTLM authentication from apex?
It is a microsoft navision webservice, I tried to do it in java following this guide and it works.

A:

I was working on a project that required SalesForce to call a service that used NTLM authentication.  I ended up writing a client implementation of NTLM in apex that you can re-use.  I've hosted it on github here: 
https://github.com/natewallace/ApexNTLM
Upload all of the classes into your org and then use the HttpClient class to send messages to your NTLM secured service.

A:

No answers so far... I'll try to summarize what I did without posting actual code (I don't have IP rights to it). Also - I know very little about MicroSoft-y world and I'm not a proper network admin either so don't shout at me if my understanding of certain things is dumbified.
Solution is written in PHP and follows excellent blog entry http://rabaix.net/en/articles/2008/03/13/using-soap-php-with-ntlm-authentication. 
Other notable sources include "Freddy's blog" on MSDN (already mentioned by OP). This is the PHP article, you can find Java and C# examples there... hell, even javascript!: http://blogs.msdn.com/b/freddyk/archive/2010/01/19/connecting-to-nav-web-services-from.aspx
Problem
As far as I know it can't be done. The WSDL files from NAV generate into Apex classes just fine (even if the names can be a bit lenghty and you need to rename Update method because it's a reserved keyword... usually I pick UpdateSingle to match UpdateMultiple).
The problem is the NTLM authentication. Salesforce can send "Basic" or "Digest"... What NAV expects is something related to Windows domain, both servers being in same LAN. Which obviously can't be done since Salesforce servers are sitting somewhere else. 
The whole thing is tricky to debug because when you access webservice endpoints with Internet Explorer NAV will happily display the WSDL and accept your handcrafted SOAP message if you have any (you can use IE Developer Tools or packet sniffer to see that this "special" authentication is used). Accessed from Firefox / Salesforce / anything that doesn't use some DLLs related to IE - boom, blank page. Originally we thought the packets die somewhere on firewall (I don't remember anymore, I think the damn thing just acts as a black hole, doesn't even return HTTP 401 Unauthorized).
And no, you can't somehow hardcode generated "NTLM key" or use some library on SF side to generate it.
Solution
I quickly hacked a proxy-like page in PHP (on a virtual machine with WAMP stack). It might not have best performance in the world but it works till today and there was no incentive to investigate if "true" proxy solution would be better. I'll keep writing about PHP - since you did your first attempt in Java you might be more comfortable with it.
I've built on Monsieur Rabaix's base with addition of config file where I'd store:

NAV dedicated integration user's username & pass
IP addresses of NAV servers (test & prod)
Salesforce "production"'s instance Id

URL-rewriting flow
Salesforce calls an endpoint (you need to manually edit the class generated from WSDL and add it to Remote Site Settings) similar to 
http://proxyPublicAddress/?
org={!UserInfo.getOrganizationId()}&
company=NAV%20Company%201&
page=NameOfPageExposedAsWebservice

Of course you can add more params as you see fit, include some authentication methods... This is the bare minimum. Your proxy needs to make decision whether to send the request to production or test NAV (that's the org), which page or CodeUnit you want to access and in which NAV Company it sits. In apex do not call anything from EncodingUtil class to encode the company name. Simple String encodedName = name.replace(' ', '%20'); is enough. 
So let's say your proxy translated it into "local address"
http://192.168.0.10:7047/DynamicsNAV/WS/NAV%20Company%201/Page/NameOfPageExposedAsWebservice

(to all non NAV-developers who happen to read it - NAV is funny and keeps data in separate schemas per each "billing entity". This entity has to be passed as part of webservice endpoint, can't be a part of SOAP payload. Obviously we don't want to generate separate Apex classes per entity so you really need to attack the endpoint variable in the output of wsdl2apex)
Header and payload transfer flow
Simple stuff really, get headers and raw SOAP message from POST data, wrap it in NTLM, get the response and send it back to SF. No need to waste cycles on parsing of this XML in any way, you can add some debug logging if you want during initial testing phase.
<?php
$requestHeaders = getallheaders();
$request = file_get_contents("php://input"); // that's raw POST data

$gateway = new NavGateway($_GET, $request, $requestHeaders); // in $_GET I'll have the URL params like "org". Constructor checks the mandatory params and builds the URL or throws back SOAP Exception
$response = $gateway -> dispatch();
$responseHeaders = $gateway -> soapClient ->__getLastResponseHeaders();

// Send back to SF the HTTP headers from NAV and the response body.
header($responseHeaders);
echo $response;

