I've actually noticed a sort of inverse diffuculty cure with the monsters in the Bestiary, U_K. Some of the lower-level ones are just plain nasty (Ioun Golem, Orichalcum Guardian/Golem, the smaller Unelementals, the lower CR Force golems...) whereas the higher end CRs are a little out of whack. (For my own purposes, I reduce them by 1/3, seems to fall in line with my own stuff a little better, but that's just guessing.)
The Void Dragon is kind of a one-trick pony, I think. That Breath Weapon is pretty much a TPK from the Great Wyrm. Plus, its tremendous speed lets it get out of danger unless the party can keep up with it (which isn't a given at that level).
The Cometary Great Wyrm likewise can be devastating, especially if you add Time Folding to its initiative (why not?). And Seventh Sense combined with Chronal Displacement give it pretty good defenses. Its only real problem is a slight lack of offense if its Breath Weapon fails, otherwise it, likewise, is a TPK at Great Wyrm status.
The Nexus...faces a serious problem. It's meant to contend with Demiurges who have, literally, SCORES of special abilities. It simply can't keep up. Yes, its breath weapon is almost a guarenteed win, but there ARE ways around it at ECL 700, and in all likelihood, the thing will die before its ever born, killed from the other side of the universe, if a Demiurge perceives it to be even a slight threat. Slipstream and Cosmic Consciousness would help a ton, I think. Transversal wouldn't hurt either.
The Neutronium Golem is...hit and miss, really. Yes, its numbers are egregiously high, but...its Initiative is +79 and its Touch AC is 88. EIGHTY EIGHT! Its DCs are...decent for about CR 400, not 9,000, which is honestly close to where I think it shoudl be. Maybe more like 600 or 700, but some of my tougher First Ones could take him down with a fair effort. For example, Zoratain, ECL 694, has 9th Sense, Perfect Defense, Trans-Attack Period, and Trans-Temporal. There's very little the golem could do to harm him, especially since his saves are around +900. I won't even get into Khorvanis, my Stage II Demiurge ECL 1,225. A Neutronium Golem wouldn't even be a speed bump for him. I'm not trying to show off or anything stupid like that either, just making the point that the golem's CR is WAY overshot.
I think a big part of the problem is that golems just aren't really suitable threats for Sidereals and up, really. A lot of things aren't. Dragons could very well be, I think, I just think they need a little boost right now (the Nehschismic category in especial) if they're going to contend with Sidereals and the like.
Now, one more thing I'd like to question. What actually constitutes min-maxing here? Is a fighter-god/sidereal taking all of the Weapon Focus/Spec, Critical/Multiplier, and Power Attack abilites min-maxing or what should be expected? I mean if you're maintaining an "average" PC a la the DMG's sample characters, then sure that makes sense, but come one, NO ONE makes a character like that, especially at these levels.
For containing power, I have a few suggestions that help my group.
1. Use only Core+Ascension. No splat books, nothing.
2. No multi-classing. 1 prestige class per character IF flavor calls for it.
3. Stay as close to HD = 1/2 ECL as possible.
4. Only one Body/Mind/Soul/Spirit line allowed per character, 2 at most if flavor absolutely demands it.
5. No Epic Spellcasting
6. Alter Reality is a Transcendental Ability given automatically to Eternals, not Sidereals.
7. Abrogate nullifes one ability of the user's choosing that they know the enemy possesses and may be changed once per round as a Free Action. (helps counter cheap abilities)
8. Sidereals and up (and all monsters in that range) have Slipstream automatically.
9. hit point multipliers are bumped up 1 step. (Right now, its Elder: x4. Old: x6, First: x8, Stage I: x16, Stage II: x32, Stage III: x64. I propose: Elder x6, Old x8, First x 16, Stage I x32, Stage II x64, Stage III x128) (These should likely apply to high-end monsters as well, or introduce d10000 HD for them.)
10. Simple understanding that the idea is for the party to be challenged. If there's an imbalance, it's up to the DM to address it. And if my players get uppity, I always have Khorvanis to fall back on (600 attacks per round @700K damage,Transversal, Uncanny Whirlwind Attack, Alter Reality 200th level spell per round, Perfect Defense, Inner Eye, Evil Eye, Deadzone, Unreal, Transcorporeal, Perfect Astro Effect, Rectify...tends to keep uppity Sidereals in line.

)
Edit: Also, I wish I could help with your 4E stuff, U_K, but I don't know the rules at all, unfortunately. I'd most certainly be up to helping out with the 3.5 conversions, though.