Oh, goody, I get to be the first one to suggest something. :) See 'a fast multipattern grep' in the Panther Book (Advanced Perl Programming), p. 74.
Your 'tail' idea is a good one, but take care not to get overrun if it gets busy. If you can syslog a marker line into the big file, that is helpful for an index.