Random trenches, no idea how?

I have a problem on my server where there are these random trenches all over the place. They are 2 blocks deep and only run North to South. Does anyone know what possibly could have caused this to happen? At the time of this happening I think I only had Essentials, WorldEdit and dynmap installed. Using CraftBukkit dev build (not sure what the build # was sorry, this was a few weeks ago).

I have tried to restore some of it using //regen but it wont restore trees and other blocks (which a few have been destroyed thanks to this glitch). Not to mention it would take an awfully long time to do all of the trenches, there are far too many!

Here's a screenshot of some of the affected area - notice the vertical lines:



I'm not really looking for a fix, just curious as to how this happened. I'll end up using regen on most of them eventually, can't say my players will find them very attractive.