Well, this particular project started getting designed in Catia, then engineered by several different people in Solidworks all seemingly in a great hurry to the point that the mess they made could no longer be boolean unioned. That’s where I stepped in. Also, there were several previous boolean operations made which left ugly small sliver surfaces, undercuts and even overlapping surfaces (which neither SW/NX complained about for some weird reason), all of which I exploded, re-trimmed and re-joined. Oh, and I also removed some fillets and then took the model into NX temporarily to re-add them (because of course Rhino failed to do them). In that process I had to battle quite a bit of micro-edges and “bad objects”, but I got it done and the model today has neither.
I’m guessing you tried Plasticity? Yeah, as noted here, Parasolid cheats with fillets up until you export it, then depending on your export settings they become more or less accurate (default NX settings, for example are horrible, while inside of NX the analytics say that everything is fine… also, NX has its own built in CNC application which will take those paths and do clean g-code for it, so who cares about tangency at that point).
Also, regarding RemoveAllNakedMicroEdges and RebuildEdges… NX has something called “optimize” which does something similar, but also replaces any sufficiently flat surface with their representation of planes, lines and so on and any sufficiently round blend with their representation of fillets, arcs etc etc. and it works very well (and then enables their “synchronous modeling” tools even if the model comes from Rhino, for example). Again, though both are very different CAD packages, I guess I’d just like a little more of the A (aid) in Rhino. 
(You may also ask why did I not just use NX for this then? Frankly, their viewport navigation is so utterly steaming pile of manure bad that the simple act of rotating around and getting into the crevices of a complex model like this would have made it take 10x longer in the end. Can you imagine that their default zoom behavior is a dolly zoom?) 