bone heat weighting: failed to find solution for one or more bones error message
Your trouble shooting is pretty good already. Other useful steps for the future are:

Append the armature datablock and the mesh datablock into a new file. Then create new armature and mesh object and select (link) the appended datablocks. Try it with these clean objects again.
Remove all vertices groups. (There was a group left called &quot;group&quot;.)
Remove the UV data.
Remove the constraints on the armature.

None of these get us any further in your case.I also tried to reproduce the problem in a controled environment and failed.
Since it works with the decimate modifier applied, we know it must be a topology error.
As batFINGER suggested you can find non manifold geometry with Select Non Manifold operation (Ctrl+AltShift+M). This will select the the non manifold geometry.
There is non manifold geometry in the tip of the tail.
Most of it doesn't cause any errors though except two vertices.
As you can see in the image, there are to vertices which are connected to overlapping faces. Delete the vertices and Parent &gt; Armature Deform with automatic weights will work.
(Click to enlarge.)