I was flying about a new world (Seed -8732934775646344018) when I came across a village (-298 599) that had generated part of it's path in a cave, even with the new cobblestone 1 layer underneath the gravel.