Blender 2.3.6a on OSX 10.6.8

What I did:
I built a terrain model and added subdiv and displacement modifiers to make it bumpy.

The problem:
When I rendered, I noticed dark triangles that are more apparent the more displacement I do.
Vertices are shared between faces (i.e. no duplicate verts), so model surface should be smooth.
I found that it is shadows by disabling them.

What I tried:
I found that it occurs with any kind of raytraced shadow light, though it's most obvious with area.
I tried applying the modifiers, but that didn't help.
I tried changing the terrain material to be very basic instead of using nodes.
I tried changing raytrace shadow settings, but could not get rid of it.
It occurs the same on version 2.62.

See attachments.