; grep --version GNU grep 2.5.3 ; time LANG=C grep asdf < lesms10.txt > ...

  ; grep --version
  GNU grep 2.5.3
  ; time LANG=C grep asdf < lesms10.txt > /dev/null
  real	0m0.025s
  user	0m0.011s
  sys	0m0.014s
  ; time /usr/local/plan9/bin/grep asdf < lesms10.txt > /dev/null
  real	0m0.082s
  user	0m0.043s
  sys	0m0.013s
  ; time LANG=en_US.UTF-8 grep adsf < lesms10.txt > /dev/null
  real	0m1.209s
  user	0m0.818s
  sys	0m0.018s

Those are the only two grep implementations I have handy. GNU grep 2.6.3 takes the same amount of time searching for 'asdf' in both locales, but searching for '.' is still slow. Thanks for pointing that out.