They should be generating relatively commonly, however I have made numerous superflat worlds with the desert preset, and in none of them, even after thorough, high-speed travel, have I found a single desert well. Though wells are not structures, I've searched in worlds with the generate structure option both on and off, but neither generates desert wells.