As far as I can tell (and this has been mentioned by other answerers already), Condition should not be thought of as a standalone function, but as a wrapper used in forming larger expressions involving patterns. But I want to stress that part of the subtlety here comes from the fact that Rule and RuleDelayed are scoping constructs. In general, scoping constructs must have a variable-binding stage, where they resolve possible conflicts in variable names and actually bind variables to their occurrences in the body of the scoping construct (or, in the r.h.s. of the rule for Rule and RuleDelayed). This may be considered a part of the inner workings of the scoping constructs, but, because Mathematica allows top-level manipulations through attributes and things like Evaluate, scoping constructs are not as black-box as they may seem - we may change the bindings by forcing the variable declarations, or the body, or both, to evaluate before the binding happens - for example, by removing some of the Hold* - attributes. I discussed these things here in somewhat more detail, although, not knowing the exact implementation details for the scoping constructs, I had to mostly guess.
Returning back to the case of Rule, RuleDelayed and Condition, it is instructive to Trace one of the examples discussed:
In[28]:= Trace[Cases[{3,3.},a_:>Print[a]/;(Print["!"];IntegerQ[a])],RuleCondition,TraceAbove->All]
During evaluation of In[28]:= !
During evaluation of In[28]:= !
During evaluation of In[28]:= 3
Out[28]= {Cases[{3,3.},a_:>Print[a]/;(Print[!];IntegerQ[a])],
{RuleCondition[$ConditionHold[$ConditionHold[Print[3]]],True],
$ConditionHold[$ConditionHold[Print[3]]]},
{RuleCondition[$ConditionHold[$ConditionHold[Print[3.]]],False],Fail},
{Print[3]},{Null}}
What you see is that there are special internal heads RuleCondition and $ConditionHold, which appear when Condition is used with Rule or RuleDelayed. My guess is that these implement the mechanism to incorporate conditions on pattern variables, including the variable binding. When you use Condition as a standalone function, these don't appear. These heads are crucial for condition mechanism to really work.
You can look at how they work in Rule and RuleDelayed:
In[31]:= RuleCondition[$ConditionHold[$ConditionHold[Print[3.`]]],True]
Out[31]= $ConditionHold[$ConditionHold[Print[3.]]]
In[32]:= RuleCondition[$ConditionHold[$ConditionHold[Print[3.`]]],False]
Out[32]= Fail
You can see that, say, Cases picks up only elements of the form $ConditionHold[$ConditionHold[something]], and ignore those where RuleCondition results in Fail. Now, what happens when you use Condition as a stand-alone function is different - thus the difference in results.
One good example I am aware of, which illustrates the above points very well, is in this thread, where possible implementations of a version of With which binds sequentially, are discussed. I will repeat a part of that discussion here, since it is instructive. The idea was to make a version of With, where previous declarations can be used for declarations further down the declaration list. If we call it Let, then, for example, for code like
Clear[h, xl, yl];
xl = 1;
yl = 2;
h[x_, y_] := Let[{xl = x, yl = y + xl + 1}, xl^2 + yl^2];
h[a, b]
we should get
a^2+(1+a+b)^2
One of the implementations which was suggested, and gives this result, is:
ClearAll[Let];
SetAttributes[Let, HoldAll];
Let /: (lhs_ := Let[vars_, expr_ /; cond_]) :=
Let[vars, lhs := expr /; cond]
Let[{}, expr_] := expr;
Let[{head_}, expr_] := With[{head}, expr]
Let[{head_, tail__}, expr_] := With[{head}, Let[{tail}, expr]]
(this is due to Bastian Erdnuess). What happens here is that this Let performs bindings at run-time, rather than at the time when function is being defined. And as soon as we want to use shared local variables, it fails:
Clear[f];
f[x_,y_]:=Let[{xl=x,yl=y+xl+1},xl^2+yl^2/;(xl+yl<15)];
f[x_,y_]:=x+y;
?f
Global`f
f[x_,y_]:=x+y
Had it worked correctly, and we should have ended up with 2 distinct definitions. And here we come to the crux of the matter: since this Let acts at run-time, SetDelayed does not perceive the Condition as a part of the pattern - it would do that for With, Block, Module, but not some unknown Let. So, both definitions look for Mathematica the same (in terms of patterns), and therefore, the second replaces the first. But this is not all. Now we only create the first definition, and try to execute:
Clear[f];
f[x_, y_] := Let[{xl = x, yl = y + xl + 1}, xl^2 + yl^2 /; (xl + yl < 15)];
In[121]:= f[3, 4]
Out[121]= 73 /; 3 + 8 < 15
If you trace the last execution, it would be very unclear why the Condition did not fire here. The reason is that we messed up the binding stage. Here is my improved version, which is free from these flaws:
ClearAll[LetL];
SetAttributes[LetL, HoldAll];
LetL /: Verbatim[SetDelayed][lhs_, rhs : HoldPattern[LetL[{__}, _]]] :=
Block[{With}, Attributes[With] = {HoldAll};
lhs := Evaluate[rhs]];
LetL[{}, expr_] := expr;
LetL[{head_}, expr_] := With[{head}, expr];
LetL[{head_, tail__}, expr_] :=
Block[{With}, Attributes[With] = {HoldAll};
With[{head}, Evaluate[LetL[{tail}, expr]]]];
What is does is that it expands LetL into nested With at definition-time, not run-time, and that happens before the binding stage. Now, let us see:
In[122]:=
Clear[ff];
ff[x_,y_]:=LetL[{xl=x,yl=y+xl+1},xl^2+yl^2/;(xl+yl<15)];
Trace[ff[3,4]]
Out[124]= {ff[3,4],
{With[{xl$=3},With[{yl$=4+xl$+1},RuleCondition[$ConditionHold[$ConditionHold[xl$^2+yl$^2]],
xl$+yl$<15]]],With[{yl$=4+3+1},RuleCondition[$ConditionHold[$ConditionHold[3^2+yl$^2]],3+yl$<15]],
{4+3+1,8},RuleCondition[$ConditionHold[$ConditionHold[3^2+8^2]],3+8<15],
{{3+8,11},11<15,True},RuleCondition[$ConditionHold[$ConditionHold[3^2+8^2]],True],
$ConditionHold[$ConditionHold[3^2+8^2]]},3^2+8^2,{3^2,9},{8^2,64},9+64,73}
This works fine, and you can see the heads RuleCondition and $ConditionHold showing up all right. It is instructive to look at the resulting definition for ff:
?ff
Global`ff
ff[x_,y_]:=With[{xl=x},With[{yl=y+xl+1},xl^2+yl^2/;xl+yl<15]]
You can see that LetL has expanded at definition-time, as advertised. And since pattern variable binding happened after that, things work fine. Also, if we add another definition:
ff[x_,y_]:=x+y;
?ff
Global`ff
ff[x_,y_]:=With[{xl=x},With[{yl=y+xl+1},xl^2+yl^2/;xl+yl<15]]
ff[x_,y_]:=x+y
We see that the patterns are now perceived as different by Mathematica.
The final question was why Unevaluated does not restore the behavior of RuleDelayed broken by the removal of its HoldRest attribute. I can only guess that this is related to the unusual behavior of RuleDelayed (it eats up any number of Unevaluated wrappers around the r.h.s.), noted in the comments to this question.
To summarize: one of the most frequent intended uses of Condition is closely tied to the enclosing scoping constructs (Rule and RuleDelayed), and one should take into account the variable binding stage in scoping constructs, when analyzing their behavior.
