<p>I'm looking for a good 3D Mesh library</p>

<ul>
<li>Should be able to read popular formats (OFF, OBJ...)</li>
<li>Should support both half-edge structure and a triangle soup</li>
<li>Should be tolerant to faults and illegal meshes.</li>
<li>Basic geometric operations - intersections, normal calculation, etc'</li>
<li>Most importantly - Should not be convoluted with endless template and inheritance hierarchies.</li>
</ul>

<p>I've tried both CGAL and OpenMesh but both fail miserably in the last point.</p>

<p>Specifically CGAL which is impossible to follow even with the most advanced code analysis tools.</p>

<p>So far I'm seriously considering to pull my own.</p>

<p>My preference is C++ but I'm open to other options.</p>

May I ask why the last point is a requirement?
Libraries written for public consumption are designed to be as generic as possible so that it is usable by the widest possible audience.  In C++, this is often best done using templates.  It would suck tremendously if found a good library, only to discover it was useless for your purposes because it used floats instead of doubles.
CGAL, for example, appears to have adopted the well-known and well-tested STL paradigm of writing generic and extensible C++ libraries.  This does indeed make it difficult to follow with code analysis tools; I doubt they're much good at following STL headers either.
But are you trying to use the library or modify it?  Either way, they seem to have some extremely high-quality documentation (e.g.
Kernel Manual
) that should make it relatively simple to figure out what you need to do, without having to resort to reading their code.
Disclaimer:  I know this isn't what you're asking for.  But I don't think what you're looking for exists.  It is
extraordinarily
rare to find open source code with documentation as good as what I've seen scanning through CGAL.  I would strongly suggest that you take another look at it.