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.