Deduction does not necessarily mean classical logic, but something more basic, which does not necessarily embody the rule of non-contradiction.
We use deduction rules in Universal Algebra or Category Theory for instance, which have little to do with classical logic, but help us to keep formal operations in order. The result does not necessarily establish truth or falsehood, but helps us decide when two items in a formal system are equivalent under a certain set of transformations.
You can look at these as logics with whole mathematical models like groups or rings or algorithms or other categories as truth values. But you don't have to. An application that is perhaps a bit broad is that of abstract semantics of computer type systems.
In that sense, some variant of deduction has to apply if you have grammar and sequences.
An anti-realist might easily imagine we live in a reality where grammar or time are not reliable touchpoints, don't behave consistently, or lack real meaning. This makes deduction still possible, but not trustworthy.
In fact many theories of meaning like those of Desaussure and Lacan insist all grammar is only approximate and not fully shareable between people, or is relatively constructed.
And some philosophical approaches to physics question whether time is real or only an aspect of perception -- most famously, Kant, and one version of the theories of Boltzmann.
@virmaior asked for an example, and the examples are fun but really boring to describe. I will try to describe one from 'fully abstract semantics', a Chomskyian linguistics model that gets adopted by computing. I hope it somewhat appeals to human beings.
One place deduction rules apply to something other than logical truth are in looking at abstract grammatical transformations (especially in computer languages, but also in human ones). The rules take us from one sentence to another, just as one might expect, and preserve meaning. Since this is not quite a logic, but only a deductive system, meaning has a broader sense than 'true, false or otherwise', and includes things we might really consider meaning.
It can be true that meaning is preserved but rendered very hard to access. So you can make a subcategory of 'reasonably efficient' such transformations. (Where reasonably efficient has to not penalize the steps in the grammar itself, so Big-O or something similar.)
It can be the fact that a transformation preserves meaning in way that sometimes is and sometimes isn't efficient, depending on the route through the transformation system. So important cases are characterized by the local equivalent of P & ~P. You can efficiently parse the statement as long as you don't take a certain detour, which will make you balk at it.
In that sense the system both does and does not handle the situation. You can address these by tuning the rules, or you can use the cases in a given language to explain why people choose given grammatical transformations over others or why grammar changes in some ways and not others.
Finding such situations is important when the language is artificial and the equivalent of determining equivalent meaning is that a given variable's type matches a function signature. (The theory arose in verifying the type system in 'ml' was not impossible to compile.) The compiler should not spend an inordinate quantity of time merely matching types and not actually compiling any code. (A real fear in the early entries in the class of languages that eventually led to Haskell.)
It has also been used to prove whether a given optimization is helpful or not. (The optimized code computes the same thing, but should do so more efficiently and not less, but the compiler should not get lost in the weeds trying to figure that out.)
(These examples are from lectures on abstract semantics by John Gray at the University of Illinois in the late 80's and early 90's, which may or may not have ever reached publication.)
If you focus on the application to a real language, there are lots of more subtle ways of looking at meaning than logics allow.
You might include considerations like the later Wittgenstein's, where meaning is focussed on given motives and segmented into 'games' in a way that does not allow all sentences to combine and reduce to truth-values, but only to 'moves' in the game.
A lot of the power of arguments in the "Investigations" derives from determining when consistency does not apply and does not matter -- where P and not P is not relevant due to the sophisticated equivalent of a category error. And I would not even consider Wittgenstein and anti-realist.
More pragmatically you can inject the idea that comprehensibility is contingent, and that incomprehensible statements still have 'best accessible meanings', so reality is constructed by your statements whether you are understood or not.
Either of these remains a world where deduction matters, but does not constitute a logic, and where consistency is not necessarily important. Since both are reasonable, we might just live in such a world.