To deduce and infer are largely interchangeable, but...
deduce is more likely to be used where you arrive at some conclusion after a more prolonged logical analysis of relevant factors (which may not even be readily apparent until actively sought out).
Whereas you often infer a conclusion almost instantly, from directly-observable factors.
Since Sherlock is the archetypal solver of complex/non-obvious mysteries, he tends to deduce...
Holmes deduced [something] (about 709 results in Google Books)
Sherlock deduced it. (186 results)
Holmes inferred it (100 results)
Sherlock inferred it (5 results)
I personally don't recognise OP's formal logical reasoning vs inspired guess distinction, except insofar as it may reflect the above tendency for deduction to sometimes be a more lengthy process.