I don't know for sure, but it looks like the interpolated surface normals (smooth normals) are to blame. If so, I don't really have any ideas how this could be fixed. But I would expect the higher subdivision levels to reduce the problem to some extent.
The reason why interpolated surface normals can cause this problem is that the normals have to be interpolated so that the facets aren't visible, but this causes the normals to be inconsistent with the surface that is geometrically visible to the renderer. It's actually the same as the terminator problem in the thread that Harvey linked to, but with a camera instead of a shadow-casting light source.
Perhaps it's something else, but the above seems like the most likely explanation. I don't really have a solution unfortunately.
Matt