When biomes are checked for structures it appears the biome check is also spanning the y axis.  So structures can fail to generate because a biome like lush caves is found and lush caves isn't a valid biome for the structure despite all the surface level biomes in the search range being valid.

The woodland mansion is the most obvious example of this occurring.  

And example is seed 15339677

A woodland mansion should generate at ChunkPos(0,2) ( /tp 0 100 32 ).  The surface biomes obviously fit the biome requirements, but at QuartPos y=9 (y=10 at some spots) (thats about BlockPos y=40) there are lush caves which appear to cause the biome check to fail.  

This is likely also affecting other structures but woodland mansions are most obvious due to the range of their biome checks.  

I suspect this may also be contributing significantly to the amount of time it takes /locate mansion to return.