Assume they're already in the worst box that various legislation (mostly related to human rights) permits you to construct, or the closest cost-effective approximation thereof.

If your argument is simply "brutality acts as a deterrent," it's almost certainly true. If your argument is, "Therefore the current level of prison brutality is optimal," or, "we should be happy with prison brutality," the only counterargument needed is that nobody's provided any evidence at all for those positions.

But if either of those is the assertion, here are some counterarguments: 1) There is a countereffect: longer (and therefore more brutal) prison sentences increase rates of recidivism. 2) Flogging and caning are brutal deterrents. Many (most?) people will take a punishment of flogging over a punishment of a long prison sentence when given the choice. Ergo at least for many, prisons are more brutal than literal torture. 3) From a cursory glance at stats, violent crime rates don't seem to be much lower in countries with higher incidences of prison rape or prison hospitalizations. I would like to see some rigorous analysis on this. 4) Violent crime rates don't seem to be much higher in countries that employ flogging or caning. Again, not a rigorous statistical analysis, but weak evidence nonetheless. 5) Let's not forget that we're trying to minimize violent crime, and prison brutality is just the perpetration of violent crime while in prison. Prisoners are people too, and many of them are innocent or overcharged. Determining optimal brutality levels will take this into account. 6) And of course I shouldn't even have to say that a large number of people undergoing the brutality of prison are completely innocent of hurting anybody at all; they are only guilty of crimes that shouldn't be crimes.

I don't think there's any evidence at all that the brutality levels in western prisons are optimal. But are they a deterrent? Yeah, sure. And the death penalty is a deterrent of shoplifting. What's the relevance to the actual debate of prison brutality? That people who applaud prison brutality have a point? Not any more than advocates of the death penalty for shoplifting do.

There's an argument (first advanced by Beccaria in the late 18th century) that it matters more that punishment be swift and certain, than that it be harsh. If people don't really believe a punishment is likely to happen to them, it won't deter reliably. Human cognitive biases being what they are, we might be better served trying to make punishment visible, rather than horrifying. Azkaban, being remote and unpleasant to think about, is perhaps less effective than some punishment that would be constantly in sight. Having the convicted criminal's wand broken. say.

Beccaria puts it much better than I could, so I'll just refer you to his essay on the topic: http://en.wikisource.org/wiki/An_Essay_on_Crimes_and_Punishments/Chapter_XXVII

In a society with veritaserum, legilimency and assorted other magic you'd think it would be straightforward to establish guilt or innocence in the vast majority of cases.

Hurting people is bad.

And I've yet to hear a good counterargument.

It's not as if you've stated the exact position you want a counterargument to: Is it "the more brutal the better"?