Can you split up the search file into smaller chunks? My experience is that grep will complain if the patterns file is too large, but there are probably tools which will simply truncate the patterns if they won't fit into the pattern buffer. If all the hits are on patterns near the beginning of the file, that would confirm this (admittedly somewhat weak) hypothesis.
If you can install
GNU grep, at least it will complain if the patterns buffer is too large. Try also adding the -F option if your zgrep supports that; or, uncompress the files temporarily, and use fgrep.
To copy message files which match one of the patterns in the patterns file, use something like
Code:
cp `fgrep -f patterns.txt -l -r /path/to/messages` /path/to/copy/to
It's much easier if you have one message per file, although there are tools to grep for messages in an mbox file of messages, too. (See if you have a tool called
mailgrep on your system. You can also run the messages through
procmail if you're familiar with that, but I'm guessing you are not, and this box is too small to begin to explain.)