Q:

How to make a session enabled ASP.NET web service work with an ajax client in a different domain?

Me and my work mate have spent lots of time finding this answer, so I thought I should share this self answered question.
I have a web service (ASP.NET 4.5) with a method that needs to use the session state. In order to archive this, I have decorated the method with EnableSession=true. This is what MS suggests to do in this article (See "Code Block A" at the end).
In order for the web service to be able to re-use the session, it needs to find a cookie with the session ID. This cookie is created and set, on the server side, by the web server itself the first time the method is called. In order to re-send this cookie with every call, MS suggests to use a "cookie container" that gets assigned to the web service proxy, saved between calls and reused with every call. (See "Code Block B" at the end).
This works great, as long as you plan to call the web service from the server side. I need to call it from the client side using a jQuery ajax JSON Post call (See "Code Block C" at the end). This code works great. In fact, the cookie with the session ID is passed to the web service automatically. No need of the cookie jar...as long as the client and the web service are on the same domain.
If the client is in a different domain (domaina.com) than the web service (domainb.com), the cookie with the session id is not passed along at all. As a result, every call to the web service is considered the first one.
I have the following headers defined on the web config to allow cross domain calls.
<add name="Access-Control-Allow-Origin" value="*" />
<add name="Access-Control-Allow-Headers" value="Content-Type" />

So, what is missing?
Code Block A: Web Service with decorated method    
public class Util: WebService {
    [ WebMethod(EnableSession=true)]
    [ScriptMethod(ResponseFormat = ResponseFormat.Json)]
    public int SessionHitCounter() {
       if (Session["HitCounter"] == null) {
          Session["HitCounter"] = 1;
       }
       else {
          Session["HitCounter"] = ((int) Session["HitCounter"]) + 1;
          }
       return ((int) Session["HitCounter"]);
    }   
 }

Code Block B: Server Side Cookie Jar Solution
<script runat="server">

    void EnterBtn_Click(Object Src, EventArgs E) 
{
  // Create a new instance of a proxy class for your XML Web service.
  ServerUsage su = new ServerUsage();
      CookieContainer cookieJar;

  // Check to see if the cookies have already been saved for this session.
  if (Session["CookieJar"] == null) 
    cookieJar= new CookieContainer();
      else
   cookieJar = (CookieContainer) Session["CookieJar"];

    // Assign the CookieContainer to the proxy class.
    su.CookieContainer = cookieJar;

  // Invoke an XML Web service method that uses session state and thus cookies.
  int count = su.PerSessionServiceUsage();         

  // Store the cookies received in the session state for future retrieval by this session.
  Session["CookieJar"] = cookieJar;

      // Populate the text box with the results from the call to the XML Web service method.
      SessionCount.Text = count.ToString();  
    }

</script>

Code Block C: Ajax Call
            $.ajax({
                type: "POST",
                url: web_services_url + "/SessionHitCounter",
                data: "{}",
                contentType: "application/json; charset=utf-8",
                dataType: "json",
                success: function (msg) {
                    alert(msg.d);
                }
            });

A:

After hours of thinking and Google searching my mate found that we were missing

An extra header ("Access-Control-Allow-Credentials")
Changing the "*" on "Access-Control-Allow-Origin" to the specific domain that is calling the web service
Adding an extra parameter on the ajax call (withCredentials)

These are the headers that are required to enable CORS 
<add name="Access-Control-Allow-Origin" value="http://localhost:53710" />
<add name="Access-Control-Allow-Headers" value="Content-Type" />
<add name="Access-Control-Allow-Credentials" value="true" />

This is the ajax call with the extra parameter 
$.ajax({
    type: "POST",
    xhrFields: { withCredentials: true },
    url: web_services_url + "/SessionHitCounter",
    data: "{}",
    contentType: "application/json; charset=utf-8",
    dataType: "json",
    success: function (msg) {
        alert(msg.d);
    }
});

