I am, in no way, the first person to suggest an "AI7" of sorts. I'm just the first one who realized that's what the false gods could be, while AI5 took the role of the farming for money.
I'm sure that's true, but the persistent lack of an AI7 is (in my opinion) a structural problem that currently has no answer.
The real problem here is that the game you want to make more challenging just doesn't have more room for it. You could make a few of the weak links like Paradox slightly harder, but that wouldn't really justify significant rewards increases.
You don't seem to want to do that though. Your first proposal included a 500 HP Miracle who basically can't be Decked out. I can see that as a desire to create something at the ABSOLUTE limit of each deck concept, and call that the end game.
A randomized pool of decks like that with current FG rules would literally beat any player deck every single time. A non-random choice, or segregated pool (put all the nature guys together and challenge, "the gods of nature," for example) would just have the most profitable choice getting hit, with all others ignored.
Within the current framework of rules, there just isn't ROOM for the challenge you want without creating something pointlessly mean-spirited/hard that players will ignore.
You say if the decks were harder, there's room to remove some FG advantages like double draw or double life, but this is only addressed in vague hypotheticals, and most FG decks completely collapse without those advantages, so EVERYTHING has to be completely redone.
Enhance the half bloods, make paradox a little harder, and dump the rest of this idea, and you have a workable idea.