As an update to this very useful question, in 2.92 I often run into this after a major sculpting session, when I'm trying to attach my mesh to an armature. Sculpting with dyntopo can give you a crazy vertex count that is easy to screw up, but we have a few new features that can come to the rescue.
"Magic button" methods like the earlier ones tend to come with a price—while triangulation and quads-from-tris works for the most part, sometimes I'll have an irrevocable count of additional triangles in my mesh which it just can't merge into quads. Remesh works reliably, but destroys the sculpture and again, gives me an absolutely unreasonable vertex count.
The Duplicate, Remesh, and Transfer Method
To begin, duplicate the mesh (Select and ⇧ Shift + D in Object mode). Then, apply Remesh to the duplicate, on sharp, with just enough iterations to cover the region of your armature's control.
Don't worry about what it does to your duplicate's geometry. (Feel free to play with the other settings if they work better in your situation.) You will now have a mesh which will reliably animate, but loses all of the character of the original.
The next step is to parent the armature to the new mesh. (Select the mesh, then the armature, then Ctrl + P). Select With Automatic Weights. You're now almost done, the new mesh should animate with your armature well.
Go back to your original, and add a Data Transfer modifier. (It should be in the top left corner for 2.92.) What this does is transfer features of a different mesh to their best match in the host mesh. You'll want to check Vertex Data and Vertex Groups, on Nearest Vertex for mapping mode. Since ultimately bone weights are just vertex groups, and we've created automatic ones for our duplicated mesh, this will copy them over to our original.
Click Generate Data Layers so it does its job. Go make a coffee, it's probably going to be a bit before it's finished. You can verify that it's doing its job afterwards, but expect significant delay, as we still need to do the next step to make it efficient—apply the modifier. Go back to your modifiers in Object mode, select Data Transfer, and hit Ctrl + A to apply it. (Again, expect a wait on this; it's just the result of your very detailed mesh, it is working.)
Once Data Transfer is applied, you can delete your new mesh and work with your original. In my experience, no matter how bad your mesh topology might be, this will do the job for animation.
For as long as the link works, I go over this in detail on my blog.
And if that doesn't work...
You can still get your hands dirty.
The other option is to pick apart your mesh by selecting part of it in edit mode, ⇧ Shift + D-ing it, and parting by selection ( P); and then trying to animate the chunk you duplicated off until you've found the location of the offending geometry. It can take a while, but it will allow you to efficiently identify the problem and make a manual change to fix it. (Remember that there are often multiple issues, not just one.) The remesh-and-transfer method above works in most cases.
