And to add more mystery:

  1 million strlens on the same random 100 byte string:
    Pentium 4 3.0GHz, gcc 4.3.2 (Debian Lenny)
      glibc:   0.52ns/char
      libc:    0.60ns/char ???
      easy:    0.94/char
      obsd:    0.94/char

I would expect libc and glibc to match being a Debian machine, and they matched on the Atom 330. I can't account for the difference here, perhaps the difference in the Debian library compilation flags and my -O3 make a difference on this processor.

Don't tell the Gentoo crowd, you'll only encourage them.