Variable scoping in Module

Question

I don't understand why $a$ and $b$ are not local in the following code:

Clear[lint];
lint[f_, x_] := Module[{a, b}, f /. Replace[x, {a_, b_} -> a -> b]];

Clear[a];
lint[x, {x, t}] (* returns t, as I would expect *)

a = 3;
lint[x, {x, t}] (* returns x *)

Clear[a]; a=3;
lint1[f_, x_] := Module[{a, b}, f /. Replace[x, {a_, b_} :> a -> b]]; (* returns t *)

It appears that the occurrence of $a$ in the pattern inside the replace is being interpreted in the outer scope. Why is that?

Update: Having read @szabolcs comment and the first answer, I still don't quite understand. First, the documentation for Rule says that "Symbols that occur as pattern names in lhs are treated as local to the rule.". Fine, that's what the comment said. But if they are local, then why is $3$ substituted for $a$ in the second example above?

Second, why does using :> solve the problem? The only difference between Rule and RuleDelayed, as far as I can see, is when the right-hand symbols are evaluated. So why does this change the behavior? (See the new fourth example above).

Answer 1

As Szabolcs say in comments, "Rule itself is a sort of scoping construct in Mathematica and it will protect symbols that are used as pattern names in its LHS from being renamed by Module." Let us check this:

Clear["`*"];
Module[{a, b}, {a_, b_} -> a -> b]

(* =>  {a_, b_} -> a -> b *)

One can see that Module has not renamed a and b as Szabolcs state. But this protection takes place only if both variables on LHS are defined via Blank (Mathematica 8.0.4):

Clear["`*"];
Module[{a, b}, {a_, b} -> a -> b]

(* => {a$_, b$96} -> a$ -> b$96 *)

Here we see a limitation of Module's cleverness...