Preamble
What happens can be understood when we recall that Rule is a scoping construct.
The general issues related to variable renamings in scoping constructs have been considered in more details in this answer.
General
Now, to this particular case. When the code runs, the external RuleDelayed considers the situation "dangerous" and performs variable renamings for your l and U variables.You end up with the code like this:
StringReplace["FooBarBazQuux",l$_?LowerCaseQ~~U$_?UpperCaseQ:>l<>" "<>U]
which can be seen using Trace. This means that the l and U on the r.h.s. are no longer coupled to the patterns on the l.h.s., thus the result.
In the first 3 cases, this doesn't happen, because the outer RuleDelayed can not "sense" the inner scoping construct (Rule in this case) - which is true even in the case Rule @@ {...}. Therefore, it does not perform the renamings. The reason why it does not care about the inner RuleDelayed is that they are completely decoupled, since no pattern variable from the outer RuleDelayed is used in the inner RuleDelayed.
This is not the case in the last example, where the more external Rule becomes coupled to the outermost RuleDelayed via the x variable. And, presumably because the system is acting rather silly in this case and considers the pattern variables l and U to belong to the Rule rather than the inner RuleDelayed (see also below for a bit more on that), we get a problem.
Simpler example, and a possible explanation
Exactly the same situation happens in this, somewhat simpler example:
{{1, 2}, 3} /. {x_List, y_Integer} :>
Rule[
Replace[x, {l_Integer, u_Integer} :> l + u],
y
]
(* l + u -> 3 *)
But what I think is really happening, is that in doing these renamings, the system acts rather silly. It interprets l_ and u_ not as parts of inner RuleDelayed, but as parts of the outer Rule. This is why it breaks the scoping / binding of inner RuleDelayed - because it is not clever enough to see that those pattern variables are localized by that inner RuleDelayed - it rather thinks that they belong to a more external Rule. And it only renames the variables inside patterns, because if you have
{x_, x+1} -> x^2
then x in x+1 will of course be taken from enclosing environment, and thus there is no need to localize / rename it.
Removing the lexical coupling
The final thing here: let us prove that the problem we have is due to a lexical coupling, in that external Rule is coupling the inner patterns with outer RuleDelayed via the y variable (in my example, and x in yours):
{{1, 2}, 3} /. {x_List, y_Integer} :>
Block[{yy = y},
Rule[
Replace[x, {l_Integer, u_Integer} :> l + u],
yy]
]
(* 3 -> 3 *)
Now, all is fine and dandy, since Block is not a lexical scoping construct, and we decouple the outer and inner RuleDelayed, even though Rule is present. Try using y in Rule[Replace[...], y] instead, and remove the Block - and we
are back to the same code as before. If you use With or Module in place of Block, the problem is still there - since they are both lexical scoping constructs, they will do the renamings in the same way as RuleDelayed.
