> Is there a sequence of fewer than 16 instructions to spot a NUL byte inside the 16 byte block?

Yes:

    pxor  %xmm1, %xmm1
    pcmpeqb (mem), %xmm1  // Do 16 byte-wise compares
    pmovmskb %xmm1, %eax  // Move results into the low 16 bits
    test %eax, %eax
    jnz saw_null