(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.