Could do this on one line of shell with the join command, except it doesn't handle compound keys, so it requires this little workaround:

sort f1 | perl -pe 's/\|/~~/' > f1~
sort f2 | perl -pe 's/\|/~~/' > f2~
join -t'|' -a 1 -a 2 f2~ f1~ \
         | perl -pe 's/~~/|/' \
         | perl -F'/\|/' -ape 's/$/|NO MATCH/ unless $#F==3; $_'
[download]

As for perl, a cool (yes, could be overkill) way would be to load these two files as tables with DBD::AnyData and just run a single SQL statement (assuming files have cols A,B,C):

  SELECT f2.A, f2.B, f2.C, COALESCE(f1.C, 'NO MATCH') as D
  FROM f2 LEFT JOIN f1 ON f1.A = f2.A AND f1.B = f2.B
[download]