If I demand that someone with whom I am having a private conversation not record it, and they surreptitiously do so, is that recording illegal?
This very much depends on where you are. Different jurisdictions have wildly different laws about this.
Some places are very permissive. You can record a conversation that you aren't even a party to so long as nobody has any reasonable expectation of privacy. In others, affirmative consent is required from every party to a conversation before it's legal to record it.
The laws run the entire spectrum. Some places allow you to record anything you're a party to without permission, but you can't record others' conversations. Some places require you to disclose, but not obtain explicit permission. Some allow you to record but restrict who you can disclose it to. Some allow you to record or ban recording only under certain circumstances. It's a really wide gamut of laws.
Since you don't say where you are, who you're recording, or why, there's no way to really answer the question. Here's a good rundown on the United States. This Wikipedia article covers lots of different countries, but only with regard to phone calls.
This is actually more than 1 question. In the state of WA, for example, it is illegal to record a conversation unless all parties agree to it. However, simply informing all parties that the conversation will be recorded and their continuing to participate in the conversation creates a legal consent on their part to record the conversation.
If you are in one of the 1-party-consent states, then any of the participants of the conversation can record it without needing any permission from anyone else. To the best of my recollection, 40 of the 50 states are 1-party-consent states. So where you are will fundamentally determine what the answer to your question is.
As another matter, if you are in a place where you don't have an expectation of privacy, you can be recorded without any participant of the conversation giving consent. What constitutes a place where you don't have any expectation of privacy may differ depending on your local laws. Some of the examples include cities in which it could be any public street, while in others it can be any public street and any place of public accommodation (stores, cafes, etc.), while in yet others it may be any government facility.
It maybe possible to deny consent to record a public performance, but in most places the only way to deny the right to record a conversation is to state that you will not have the conversation unless all other parties affirmatively agree to not record it.
There is a division in the US between 1-party consent laws and all-party consent: it's clearly legal in the case of a 1-party consent jurisdiction. If you are in Washington, it may be against the law, then again, maybe not. Washington is an all-party jurisdiction, but the law prohibits recording a
Private conversation, by any device electronic or otherwise designed to record or transmit such conversation regardless how the device is powered or actuated without first obtaining the consent of all the persons engaged in the conversation
The statutory consent requirements look fairly tight:
Where consent by all parties is needed pursuant to this chapter, consent shall be considered obtained whenever one party has announced to all other parties engaged in the communication or conversation, in any reasonably effective manner, that such communication or conversation is about to be recorded or transmitted: PROVIDED, That if the conversation is to be recorded that said announcement shall also be recorded.
Observe that parties do not have to say anything like "okay" to have consented, they simply have to speak, knowing that they are being recorded. As decided in State v. Townsend, 57 P.3d 255, such consent can also be "implied" (not via the aforementioned statutory loophole). This case involved electronic messages, which are by nature "recorded" multiple times in the course of transmitting the message (plus, an illegally recorded communication cannot be used as evidence). The court finds that:
a communicating party will be deemed to have consented to having his or her communication recorded when the party knows that the messages will be recorded
The crux of the decision comes down to the point that the person being recorded should have known that he was being recorded, yet continued to communicate (thus, consented). Making a distinction between "knows that it will" and "knows that it may" is unlikely to gain much legal traction.
California, another all-party state, says (Cal Penal Code 632) that one
who, intentionally and without the consent of all parties to a confidential communication ... records the confidential communication...shall be punished...
The California statute directly address what is a confidential communication (private conversation):
(c) For the purposes of this section, “confidential communication” means any communication carried on in circumstances as may reasonably indicate that any party to the communication desires it to be confined to the parties thereto, but excludes a communication made in a public gathering or in any legislative, judicial, executive, or administrative proceeding open to the public, or in any other circumstance in which the parties to the communication may reasonably expect that the communication may be overheard or recorded.
Under the described circumstance, if a party suspects that they may be recorded, then they reasonably expect that the communication may be overheard. That expectation can be defeated if the other party promises not to record, but not if you announce a prohibition against recording (you have no authority to compel an outcome). By continuing to speak in the face of a lack of response to the question, you may be deemed to have given consent.
The only way to know for sure is to look at how the courts treat implied consent in an all-party jurisdiction when the offended party articulates a suspicion that the communication is not private and does not receive an assurance of privacy, as you describe. I don't know of any case that definitively answers that question.