Creases caused by internal faces (The title reflects the fact that this issue has been fixed. This makes it easier for others to search, I think.)

I have a mesh with unusual creases on both arms and one under the head. This pervades all of my models across multiple versions of Blender. This is version 2.77a.

1: Edit mode is shown. Original vertices are shown.
2: Object mode is shown. Smooth shading is off.
3: I removed all double vertices, which removed no vertices because I had no doubles.
4: I made all normals face outwards, but it isn't the cause.
5: Don't make me triangulate the mesh because it's no good.
6: Don't tell me to use edge split with subsurface. It separates the mesh on the odd boundaries.

Everything is made with quadrilaterals only. Changing the shading from smooth to flat or vice versa on faces/edges/vertices has no effect. Triangulating the mesh only produces stranger subsurface results. There are no marked seams and I cleared them anyway. All normals face outward.

I've visited these places without success: http://feeblemind.tuxfamily.org/blog/index.php?post/2007/08/13/88-how-to-solve-blenders-smoothing-problems, How to smooth shade an object while retaining hard edges?, Keep sharp edges when using subdivision surface, https://blender.stackexchange.com/questions/38828/shading-normals-problem, Weird smooth shading.
This issue is caused by having extra edges or faces between contiguous edges or faces in a mesh. In this case, I had extra faces where I extruded off of quad faces.



An example of extra edges is shown, where the orange line is an extra edge because it doesn't contribute to the face data. Edges that don't cross faces and don't contribute to face data will cause the subsurface modifier to have issues, since it checks edges and faces without regard to their usefulness.



(Answered originally by Denis)