It seems FindInstance uses different methods to find 1 instance and to find more than one instance.
constraint = {a > 0, b >= 0, c >= a + b, a >= c/4};
Trace[
FindInstance[constraint, {a, b, c}, Integers, 1],
_Reduce`LinearDiophantineInstance | _Reduce`ReduceInstance,
TraceInternal -> True
]
Trace[
FindInstance[constraint, {a, b, c}, Integers, 2],
_Reduce`LinearDiophantineInstance | _Reduce`ReduceInstance,
TraceInternal -> True
]
LinearDiophantineInstance returns quickly, even on the 9-variable problem. The second call to ReduceInstance in the 2-instance case takes a long time, which is easy to believe given the complexity of the auxiliary system. In the 9-variable case, I only waited a few minutes while, I assume, it was building the argument for a second ReduceInstance call.
I do not know whether there is a reason to use ReduceInstance instead of nested calls to LinearDiophantineInstance, similar to Mr.Wizard's approach. Given that it handles both of the examples, it seems unlikely.