This has been discussed endlessly (as you know ) and my favorite proposed solution is to use fines collected from criminals (foreign and domestic) to fund national defense, courts, and police. It's also arguable that a flat tax, imposed on all citizens equally, is a fair method of preventing the fraud/abuse of free riders. I know ya'll AnCaps will never accept that, but want to put it out there to clarify where we differ.
As for the fines from criminals, I am here actually going to borrow from a Anarcho-syndicalist critique of AnCap. It was incorrect in applying it to AnCap, but by that same token, it applies perfectly to the "night watchman" State. In such a system (the State funded entirely from fines from criminals) there would be a drive, perhaps even a necessity, to both broaden the scope of fine-able offenses, and to steepen the fines. Compare the current practice of asset forfeiture, and you see my concern.
The only way to fund such a State without encroaching on rights is voluntarily, through subscriptions. And indeed, there may be (small, or sparsely populated) areas where it is natural for there to be only one provider... and though it would have a natural monopoly, the defining characteristic of a "State" is that it's monopoly is absolute... it brooks no competition on it's territory. A market provider of Security would not have the ability to force it's competitors out of the region, so while you might get something that looks very much like a State, it would actually be nothing of the sort.
Looking forward to it.
My most glaring concern with Nozick's theory - albeit at first glance, without having yet read the book - echoes Rothbard's: Since Anarchy is required for such a "justified" state to develop, then proponents of the minimal state should be pushing just as hard for a market anarchy as the staunchest AnCaps. You have to take the flag all the way up, before bringing it back to half-mast.