I will provide one solution which will be using ANSI C and LibraryLink. Needless to say that this is speeder...(Platform: MacOSX, gcc 4.2)

The preparations are the same as in Leonid's answer.

**Implementation**

    dayofweek = "
    #include \"WolframLibrary.h\"
  
    DLLEXPORT mint WolframLibrary_getVersion(){
       return WolframLibraryVersion;
    }
  
    DLLEXPORT int WolframLibrary_initialize( WolframLibraryData \
      libData) {
  	return 0;
    }
  
    DLLEXPORT void WolframLibrary_uninitialize( WolframLibraryData \
      libData) {
  	return;
    }
  
    #define _LEAP_YEAR(year)  (((year) > 0) && !((year) % 4) && \
        (((year) % 100) || !((year) % 400)))
  
    #define _LEAP_COUNT(year) ((((year) - 1) / 4) - (((year) - 1) / \
        100) + (((year) - 1) / 400))
  
    const int yeardays[2][13] = {
      { -1, 30, 58, 89, 119, 150, 180, 211, 242, 272, 303, 333, 364 },
      { -1, 30, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 }
    };
  
    const int monthdays[2][13] = {
      { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
      { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
    };
  
    int weekday(int year, int month, int day)
    {
      int ydays, mdays, base_dow;
      /* Correct out of range months by shifting them into range (in the same year) */
      month = (month < 1) ? 1 : month;
      month = (month > 12) ? 12 : month;
      mdays = monthdays[_LEAP_YEAR(year)][month - 1];
      /* Correct out of range days by shifting them into range (in the same month) */
      day = (day < 1) ? 1 : day;
      day = (day > mdays) ? mdays : day;
      /* Find the number of days up to the requested date */
      ydays = yeardays[_LEAP_YEAR(year)][month - 1] + day;
      /* Find the day of the week for January 1st */
      base_dow = (year * 365 + _LEAP_COUNT(year)) % 7;
      return (base_dow + ydays) % 7;
    }
  
    DLLEXPORT int dayOfWeek(WolframLibraryData libData,
  			mint Argc, MArgument *Args, MArgument Res) {
  	  mint I0, I1, I2;
  	  I0 = MArgument_getInteger(Args[0]);
  	  I1 = MArgument_getInteger(Args[1]);
  	  I2 = MArgument_getInteger(Args[2]);
  
  	  MArgument_setInteger(Res, weekday(I0, I1, I2));
  	  return LIBRARY_NO_ERROR;
    }
    ";

**Create the Library and load it**

    lib = CreateLibrary[dayofweek, "dayOfWeek", CompileOptions -> "-O3 -funroll-loops"];
    dow = LibraryFunctionLoad[lib, "dayOfWeek", {Integer, Integer, Integer}, Integer];

For CL (Microsoft's compiler has similar options with different naming...)

**The dayOfWeek function**

    Clear[dayOfWeek];
    dayOfWeek[dates_List] := 
       dow[#[[1]], #[[2]], #[[3]]] & /@ 
          Transpose@{#[[All, 1]], #[[All, 2]] - 1, #[[All, 3]]} &@dates

**Timing**

    {0.067380,{6,5,6,6,3,2,0,0,4,6,4,3,5,3,4,6,6,<<99966>>,...}}

**Conclusion**

As the argumentation holds to use Java, because of it's simple interface I think I've shown that this holds as well for C/C++ and is unbeatable fast.