Out of curiosity are you using the Malevolent ideology approval building? I've found it to be pretty powerful on Insane maps. That said I haven't gotten an empire quite that large yet.
Approval is computed as
([flat morale bonuses] - 0.2 * [number of planets]) * (1 + [approval bonus]) / [planetary population]
If the large empire penalty is large enough to reduce the planet's flat morale bonuses to zero or less, the Intimidation Center will not help you; it provides +50% approval and +10% approval per level, but +50% (or +100%, or +100000%) of any number less than or equal to zero is still going to give you a final approval rating of 0%.
Personally, I feel that the large empire penalty in GCIII is poorly implemented; penalizing approval is simply an indirect way of targeting manufacturing (which I tend to feel should be more or less unaffected; my factory takes longer to produce goods locally from locally-sourced resources with local labor because why, exactly?), research (which I feel would be better targeted by going after tech costs), income (which already has a size-dependent penalty in maintenance, though it's arguably the case that the maintenance costs are too low), and then penalties to growth/influence/resistance which are either trivially easy to counter or not really worth bothering about since the approval-related modifiers to these last three stack additively with the bonuses you can obtain for those from improvements. On top of that, I feel that the current large empire penalty over-encourages the taking of the flat morale bonuses in the Governance specializations and significantly reduces the value of farms on larger maps.
