I've tried everything that's possible within the "edit object" window. Yesterday I had the same problem with a completely different mesh that I made myself. One part of the mesh was a boolean (a box with another box clipped out of it) and that part of the mesh object was heavily speckled - much worse than in the examples above. When I split the object by materials, the speckles vanished. With the mesh shown above, splittling by materials has no effect. It's very weird, and I say it's a bug. It just shouldn't happen, and it doesn't in other render engines.