Name: Rolf Mertig Date: 03/01/12-03:08:12 PM Z

This is just how /. (ReplaceAll) works.
>From http://reference.wolfram.com/mathematica/ref/ReplaceAll.html

ReplaceAll looks at each part of expr, tries all the rules on it, and then goes on to the next part of expr. The first rule that applies to a particular part is used; no further rules are tried on that part, or on any of its subparts.

---
So, all what is need is to change /. to //. :
In[1]:= !!pol2.m
<<HighEnergyPhysics`FeynCalc`
Print[" "];
(*
{$AL[1], $AL[2]} = {mu, nu};  (* $AL are predefined dummy indices *)
*)
FI; IP = InputForm;
constraint = {
   FeynCalcInternal[
     FV[e2, muPAT] FV[e2, nuPAT] ->
      PolarizationSum[mu, nu, p2]] /. {muPAT :> mu_, nuPAT :> nu_},
   FeynCalcInternal[
     FV[e4, muPAT] FV[e4, nuPAT] ->
      PolarizationSum[mu, nu, p4]] /. {muPAT :> mu_, nuPAT :> nu_}};
M = SP[p1, e2]^2 SP[p2, e4]^2
tmp = Uncontract[Expand[M], e2, e4, Pair -> All, Unique -> False];
Print[" "];
Print["check constraint : ", IP@constraint];
Print[" "];
Print["contract and using the constraint : ",
 IP@FeynCalcExternal@Contract[tmp //. constraint]] 
In[1]:= <<pol2.m
Loading FeynCalc from /home/rolfm/HighEnergyPhysics
FeynCalc 8.1.0 Type ?FeynCalc for help or visit http://www.feyncalc.org/
$PrePrint is set to FeynCalcForm. Use FI and FC to change the display format.
Loading FeynArts, see www.feynarts.de for documentation
FeynArts 3.4 patched for use with FeynCalc
 
 
check constraint : {Pair[LorentzIndex[mu_], Momentum[e2]]*
    Pair[LorentzIndex[nu_], Momentum[e2]] -> 
   -Pair[LorentzIndex[mu], LorentzIndex[nu]] + 
    (Pair[LorentzIndex[mu], Momentum[p2]]*
       Pair[LorentzIndex[nu], Momentum[p2]])/Pair[Momentum[p2], Momentum[p2]]\
   , Pair[LorentzIndex[mu_], Momentum[e4]]*
    Pair[LorentzIndex[nu_], Momentum[e4]] -> 
   -Pair[LorentzIndex[mu], LorentzIndex[nu]] + 
    (Pair[LorentzIndex[mu], Momentum[p4]]*
       Pair[LorentzIndex[nu], Momentum[p4]])/Pair[Momentum[p4], Momentum[p4]]}
 
contract and using the constraint : 
 (-SP[p1, p1] + SP[p1, p2]^2/SP[p2, p2])*
  (-SP[p2, p2] + SP[p2, p4]^2/SP[p4, p4])