Recalculating and flipping normals not working—but manually re-adding the faces does? (Simple mesh)
The mesh has some inside faces, and Blender is confused by it :).  


Select the inside faces through Select > All by trait > Inside Faces
Delete them with X > Faces
Done.




Credits to @John for finding the best solution for his own problem :).