[L]egitimate governments generally consider murder a fairly serious crime, and refuse to enforce contracts which would require illegal activity of the signatories. I'm comfortable with having the libertarian principle superceded by criminal law.

Read literally, this means that you're OK with any violation of the libertarian principle, as long as this violation happens to be formally codified as part of the criminal law. Is that really your position?