Este é fácil:
grep -E "199[5-9]"
faz o trabalho. É fácil, porque o intervalo de números pretendido corresponde a um intervalo de código de caracteres. Para um exemplo mais complicado, por exemplo, 1998-2003, você terá que dividir o intervalo apropriadamente:
grep -E "199[8-9]|200[0-3]"