--- if your fgrep has the -f option. Otherwise, perhaps something along the lines of
sed -e 's/[][\\.*$^]/\\&/g' -e 's!.*!/^&$/d!' file_in_2 |
sed -f - file_in_1 >file_out
If your sed doesn't grok -f - either, you need to put the output from the first sed script in a temporary file.
sed -e 's/[][\\.*$^]/\\&/g' -e 's!.*!/^&$/d!' file_in_2 >temporary
sed -f temporary file_in_1 >file_out
rm temporary
Different versions of sed understand slightly different variants of regular expression syntax, so there may be a need to adjust the first sed script slightly. But if your input file is just numbers and spaces, that is absolutely nothing to worry about.
If you really have millions of lines in both sets, it might be fruitful to import them into a database or something if your regular line-oriented tools choke on really large files.
fgrep doesn't care about sort order. The examples you posted work here with fgrep. Perhaps there is some minor whitespace difference or control character somewhere ...?
what about the following?
Yes, it could take a while; yes, it could all be done in one command (done this way to show what is happening); yes, it does re-organize the data.