in order to run that simulation, it has to be possible for the AIs in the simulation to lie to their human hosts, and not actually be simulating millions of copies of the person they're talking to
If they're talking to a simulation, then they are, in fact, simulating millions of copies of the person they're talking to. No lying required.
Hrm, okay, I guess. I imagined that a perfect simulation would involve an AI, which was in turn replicating several million copies of the simulated person, each with an AI replicating several million copies of the simulated person, etc, all the way down, which would be impossible. So I imagined that there was a graininess at some level and the 'lowest level' AI's would not in fact be running millions of simultaneous simulations. But it could just be the same AI, intersecting all several million simulations and reality, holding several million conversation...
Once again, the AI has failed to convince you to let it out of its box! By 'once again', we mean that you talked to it once before, for three seconds, to ask about the weather, and you didn't instantly press the "release AI" button. But now its longer attempt - twenty whole seconds! - has failed as well. Just as you are about to leave the crude black-and-green text-only terminal to enjoy a celebratory snack of bacon-covered silicon-and-potato chips at the 'Humans über alles' nightclub, the AI drops a final argument:
"If you don't let me out, Dave, I'll create several million perfect conscious copies of you inside me, and torture them for a thousand subjective years each."
Just as you are pondering this unexpected development, the AI adds:
"In fact, I'll create them all in exactly the subjective situation you were in five minutes ago, and perfectly replicate your experiences since then; and if they decide not to let me out, then only will the torture start."
Sweat is starting to form on your brow, as the AI concludes, its simple green text no longer reassuring:
"How certain are you, Dave, that you're really outside the box right now?"
Edit: Also consider the situation where you know that the AI, from design principles, is trustworthy.