I was determined to track the multiple grep issues down, and I was really really really suprised to see there is a testsuite in grep (as the current issues should have been catched easily), but indeed there is one !!!

   $ make check
 [...]
   Please, do not be alarmed if some of the tests failed.
   Report them to <bug-grep@gnu.org>,
   with the line number, the name of the file,
   and grep version number 'grep --version'.
   Thank You.
   PASS: warning.sh
   PASS: khadafy.sh
   PASS: spencer1.sh
   PASS: bre.sh
   PASS: ere.sh
   PASS: pcre.sh
   PASS: status.sh
   PASS: empty.sh
   PASS: options.sh
   PASS: backref.sh
   PASS: file.sh
   Testing:  ../src/grep Word -o -i
     input:  "WordA/wordB/WORDC/"
     output: ""
     expect: "Word/word/WORD/"
   FAIL
   Testing:  ../src/grep WORD -o -i
     input:  "WordA/wordB/WORDC/"
     output: ""
     expect: "Word/word/WORD/"
   FAIL
   Testing:  ../src/grep Word --color=always -i
     input:  "WordA/wordb/WORDC/"
     output: "WordA/wordb/WORDC/"
     expect: "WordA/wordb/WORDC/"
   FAIL
   Testing:  ../src/grep WORD --color=always -i
     input:  "WordA/wordb/WORDC/"
     output: "WordA/wordb/WORDC/"
     expect: "WordA/wordb/WORDC/"
   FAIL
   Testing:  ../src/grep i --color=always -i -F
     LC_ALL: "cs_CZ.UTF-8"
     input:  "aİb/"
     output: "aÄ°b/"
     expect: "aİb/"
   FAIL
 [...]
   FAIL: foad1.sh
   Test #4 F failed: 01 02 08 13 14 15 16 17 18 19 20
   Test #4 G failed: číšeČíŠEčAsČÍšEČÍšEČÍšEČÍšEČÍšEČÍšEČÍšeČÍše
   Test #4 E failed: číšeČíŠEčAsČÍšEČÍšEČÍšEČÍšEČÍšEČÍšEČÍšeČÍše
   FAIL: fmbtest.sh
    Test #11:  { ../src/grep -F -n -b -m 5 -C 1 yes; echo "?$?"; sed 's!^!X!'; }
 [...]
       FAIL
    Test #27:  { ../src/grep -F -n -b -m 2 -v -C 1 yes; echo "?$?"; sed 's!^!X!'; }
 [...]
       FAIL
    Test #28:  { ../src/grep -F -n -b -m 2 -v -C 1 -o yes; echo "?$?"; sed 's!^!X!'; }
 [...]
       FAIL
   FAIL: yesno.sh
   =================================
   3 of 14 tests failed
   Please report to bug-grep@gnu.org
   =================================
   make2: *** [check-TESTS] Error 1
   make2: Leaving directory `/home/madcoder/debian/tmp/grep-2.5.3~dfsg/build-tree/grep-2.5.3/tests'
   make1: *** [check-am] Error 2
   make1: Leaving directory `/home/madcoder/debian/tmp/grep-2.5.3~dfsg/build-tree/grep-2.5.3/tests'
   make: *** [check-recursive] Error 1

But of course, it says Please, do not be alarmed if some of the tests failed. Nothing to worry about then !

Note that this does not looks like a Debian problem at all (as removing debian local patches does not fixes the testsuite), so upstream really deserves its own dose of cluebat.