Straight after I hit submit, spacebat of #emacs pointed out
grep-use-null-device inside grep-host-defaults-alist which is
populated by grep-compute-defaults in grep.el:548.

From my understanding of that code, it's trying
    grep -nH ^English /usr/share/emacs/24.3/etc/HELLO
on the remote host, which fails because emacs is not installed there,
though GNU grep is and grep does support -H.