Oddly enough, this solved the problem. I attacked him, found he was marked essential, got arrested, paid my fee... And found the victim wandering off to the relevant location a few minutes later. Was therefore able to stop the murderer and complete the quest. Even got the decapitation animation when I intervened.
Granted, the heroic image was somewhat tarnished by the fact that I basically looked like the Witch King of Angmar hacking down a civilian, but it still counts...