Well I tried it on an IvyBridge Xeon E5-2680-V2, gcc version 4.4.3 with -O3, table size = 32. Single table at a time ends up being faster:

    155 M searches / sec for one table at a time.

    108 M searches / sec for two tables at a time.

    88 M searches / sec for four tables at a time.

The interleaved version of the code looks like this (for two at a time):

    #define LOGSIZE 5

    unsigned dsearch (unsigned key, unsigned * vector)
    {
        unsigned size = (1 << LOGSIZE) / 2;
        unsigned * low1 = vector;
        unsigned * low2 = vector + ((1 << LOGSIZE) / 2);
        unsigned i;

        for (i = LOGSIZE - 1; i != 0; i--) {
                size /= 2;
                unsigned mid1 = low1[size];
                unsigned mid2 = low2[size];
                if (mid1 <= key)
                        low1 += size;
                if (mid2 <= key)
                        low2 += size;
        }

        if (*low2 == key)
                low1 = low2;

        return low1 - vector;
    }

The compiled code ends up branch free (gcc does a good job), but is 30 instructions instead of 18.

Oh well, was worth a shot..