Not sure what would work well within the game yet, but would this be a reasonable balance? 'Cause I can certainly see the idea of "Well, if you kill someone, that's usually not what you want, and it has ugly nonmagical consequences" not being nearly enough deterrent to balance the difference in difficulty...
Ooh, unless the consequences were
explicitly that—that killing someone using magic
always attracts more notice and gets you into more hot water, no matter the circumstances. Cosmic justice of a sort.