Right it appears (as far as I can tell so far) to be that newly generate land is OK.
The problem seems to be contained within the "original" spawned land where I had originally set Dungeons and Caves to off.
I had modified the database some time ago to allow new areas to contain Dungeons and caves. Which had worked fine.
It appears though that since the latest update, the areas where there were originally no caves and dungeons now have caves and dungeons! Which is great, but it seems that this is the process which has caused the holes.