Due to the sampling pattern used by RegionPlot, it is lucky that it finds the line in your first example. Consider the output of
noisyFunction[x_, y_] := Module[{},
Sow[{x, y}];
x - y
];
ListPlot[
Take[
Reap[
RegionPlot[noisyFunction[x, y] == 0, {x, 0, 100}, {y, 0, 100}]
][[2, 1]],
{4, -1}]
]
The clustering of samples around the line is easily seen. But RegionPlot is not lucky for your second example.
ListPlot[
Take[
Reap[
RegionPlot[noisyFunction[x, y] == 1, {x, 0, 100}, {y, 0, 100}]
][[2, 1]],
{4, -1}]
]
One should use EvaluationMonitor if one is going to be serious about inspecting the evaluation set of a function fed to a plot or numerical search.