We don't have nearly as many polygons as you do, but we have successfully used topology to find overlaps, gaps, etc. We have three feature datasets involved, with about (guessing) 15 different rules. Although we don't have have a lot of polygons, the vertices are quite dense. We also have many exceptions to the rules, and topology allows us to mark those.
At least with our topology checks, the process is done in an ArcEdit session (versioned)...I'm not sure (can't remember) if this can be automated with python or not, although the setting up of the rules was. Our geographic extent is large (Alaska, including the Aleutians) so the "cleaning" of the topology can take hours, but it can be done in smaller chunks to speed up the time between saves. The areas you have not checked remain as "dirty" areas.
The errors you find can be sorted and filtered, including by the current extent, and you can double-click to zoom into the area. If I remember correctly, you can even reselect them and export/save them to a new feature class if needed.
With your millions of polys, this might not be a practical solution, but it does work. For me, that's saying something since I came from the coverage topology world, and getting the topology to work for us was required for us to move (which we did quite a while ago now).
So, faster? maybe not. Ability to break into smaller sessions so the overnight offline isn't an issue? maybe.