HttpWebRequest with certificate

[C# Programming]

Hi.

I have 2 applications:
One is simple windows application and the other is web service.
They are both on the same machine, windows server 2003 - SP2.

exactly the same code in both:
X509Certificate Cert = X509Certificate.CreateFromCertFile("...some path\\export.cer");
HttpWebRequest Request = (HttpWebRequest)WebRequest.Create("https://...some URL...");
Request.ClientCertificates.Add(Cert);
Request.UserAgent = "Client Cert Sample";
Request.ProtocolVersion = HttpVersion.Version11;
Request.KeepAlive = true;
Request.Method = WebRequestMethods.Http.Post;
..
byte[] postBytes = Encoding.ASCII.GetBytes(strRequest);
System.IO.Stream requestStream = Request.GetRequestStream();
requestStream.Write(postBytes, 0, postBytes.Length);
requestStream.Close();
..
HttpWebResponse Response = (HttpWebResponse)Request.GetResponse();

In the windows application (running under logged in user) - I get response and all OK
In the web service (running under NETWORK SERVICE) - I get errors:
{"The underlying connection was closed: An unexpected error occurred on a send."}
{"Authentication failed because the remote party has closed the transport stream."}

Checking with the other side (who gets my requests) it seems like when I'm sending from the windows application they get the request with the certificate and in the case of web service they get the request without the certificate.

In the machine that sends the both requests, in the certificate store, the certificates are stored in: "Certificates (Local Computer) --> Personal --> Certificates".

Any ideas why is one sending the certificate and the other doesn't?