What are the reasons why automatic normal recalculation might fail
I had a series of models in a Blender file where the Mesh Normals were pointed both inward and outward. Pressing Recalculate Normals fixed a few of the 15000 faces but not all. Trying to select inward faces failed, nothing lit up after trying to select them. 
I found that the recalc would fail if the model had doubles or had Non Manifold mesh.  Deleting the doubles and removing the non manifold meshes was the answer. Once gone, the Recalculate repaired all the inward facing faces.