The AI's first goal has to be winning. If you're the top in technology you're going to be spied upon. The only thing you can do is make it as difficult as possible with spy defense buildings and hope your counterspies kill their agents.
Futhermore, demands on AI will only work if you are threatening to them. I'd wager that Genghis has a very high threshold determining whether or not you intimidate him militarily.
Either way, however, the AI will do whatever it feels necessary to advance on a path to victory. In my just finished game with the Byzantines, Spain and China both DoW'd me despite being completely outmatched. Both were pinned in and viewed my "elastic defense" (very few border troops but all other troops plus fast movers a turn or two away) as an opportunity. I crushed them both without losing a unit, but it was the only path they saw to victory so they had to "go all in".
In the end, consider a winning AI like people see the US. Powerful and advanced, but easy to overextend due to the years of enemies. Ignore their demands and denunciations if you have the ability to defend yourself from their troops via distance, terrain, or defensive military parity. Consider a losing AI like North Korea. Everyone knows how irrelevant they are, but they're going to do whatever they darn well feel is in their best interest (because fighting them would cost more than it's worth to have them stop).
Does Genghis deserve death or can you afford to lose a tech every 80 or so turns while he's still behind you about 10 techs? If death then gear for war and end him. If cake then forgive him for the positive modifier and hope he can funnel money or luxuries to you via neutral or friendly status every 30 or so turns.
Why does the AI's goal have to be winning? A lot of the complaints about the AI stem around this; friendly AI, who has nothing but positive modifiers for years, will backstab you, send their units to suicide, and then become a sitting duck. What sensible leader is dumb enough to declare war against the US, using your modern day example? The last nation that did it - Japan - got sorely destroyed in the effort, and they had a much stronger chance than most of the AI in game do at winning it.
The AI's first and foremost goal should be self-preservation. Then it should consider how it wants to run its empire. I would say the general consensus is that most empires in history have wanted to expand - this is not a bad thing, and the AI should consider this. However, as time passes on, and society gets more..."civil", if I should dare say that, the AIs should be more cautious when considering hostilies. The ancient times were filled with warfare; just look at Mesopotamia for an example. Wars in the Medieval era were more religious based, and in the Industrial era, they were more imperialistic. By the Modern times, wars become much less common, and their objectives are usually clear: resource obtaining, dictator removal or alliances.
Now imagine if the AI pursued those types of goals. If religious civilizations pursued wars because of religion, if Industrial civilizations preferred exploration and imperiaism, if modern civilizations formed alliances with each other, and hostilities brewed that eventually lead to world wars. Would that not lead to a better game experience? These are the things diplomacy is needing, justification for war. Right now, war is essentially "You're winning, this is a desperation act to try to stop you", among other example. Would it not be fun to fight wars because of empire-specific things, not some arbitrary game condition?
I realize this would make victory too easy, but that's a tradeoff I would be willing to accept. It's best to immerse the player, not make them feel like they are playing a boardgame. As demonstrated by a lot of diplomatic complaints, I'd say a healthy portion would agree with me here.
I'm sorry I just ranted. Mostly more on topic, it's not a bug that the AI wants to continue spying on you after lying about it. The AI is looking out for its best interests, as anybody would. You're more likely to declare war/denounce if he refuses your demand, so to appease you he lies to keep you happy for a bit longer. (a smarter strategic AI would build an army and defenses up in preparation for war after this event)