I should point out that, in classic fluff, the Adeptus Arbites did not prosecute normal crime. They only prosecuted crime that was committed against the Imperium, and could not care less about crime - to include felonies or even capital crimes and such - that fell under the planet's "jurisdiction".
This is the reason why Precincts were typically described as having only a hundred or so Arbites and perhaps only one Judge per planet. The sort of crime I can imagine them investigating?
1. Crime against any branch of the Adeptus Terra.
2. Crime that interferes with the planetary Tithe.
3. Crime committed by members of the planetary government (rebellion, piracy, interstellar smuggling, etc.).
4. Crime committed against the planetary government (protests, sedition, rebellion, piracy, interstellar smuggling, etc.).
Know what I mean? It would have to be pretty heavy stuff - or, ironically enough, even petty crime... so long as it involved the Adeptus Terra or other authorities of the Imperium. Local cops (perhaps modeled after the Adeptus Arbites) would handle anything that started and ended within the planet and didn't involve Imperial authorities. I'm not saying an Arbites would watch a murderer gun down normal people and do nothing. If someone ran out of their shop screaming that someone robbed them, though? I doubt the Arbites would bat an eye.