This is unbearably slow for large files. I'd like to search without having to convert to/from hex. ... It's the conversion to hex that takes all the time.

Two thoughts:

1. You're doing entirely too many read()'s. Reading 16 bytes at a time is underkill, since a disk block is going to be at least 512 bytes. Try reading 512 bytes at a time.
2. Instead of using sprintf to make hex strings, roll your own table lookup. It'll be a lot faster.

  while ( read(FILE, $buf, 512) ) {
      foreach ( $buf =~ m/./gs ) {
          $binhex .= $hex[ord($_)];
      }
  }
[download]

Setting up @hex is left as an exercise.

Oh, and if you're on Win32, don't forget to   binmode(FILE);