A structure may get generated with some square sections at different heights.
What I saw (presumably buggy)
I found a malformed temple as shown in screenshots in world with seed -807116175. That is, one square section of the temple is at height 1 block lower than the rest of the temple. The shift lines cross at exactly center-chunk (-984,-312), and the temple is created in 4 parts (depending on approach directions, though, but can be witnesses with map programs). I remember that I did first travel diagonally so that I saw only a part of this temple on a map, and later returned to check the temple and thus caused the generation of the rest of the area and the temple. Alas, I do not remember the order or directions of moving I happened to use.
However, I have not been able to reproduce the result with several tries, with generating the different chunks at different orders (by teleporting to different locations far away from the temple and then approaching).
What I expect
That all structures would be without weird level shifts. (Except perhaps in a case where the surrounding environment has similar shift, so it would sort of depict the result of an earthquake or something).
The other tries to reproduce the problem always generating the same temple in a way I would expect seems to indicate that the bugged version is indeed bugged, and not intended.
The only reason (and I admit a weak reason) for this I have been able to think by reading the code, is that somehow the structure generator estimates the ground average heights differently for different sections. Using MCP naming: MapGenStructure.generateStructuresInChunk() -> ... ComponentScatteredFeature.(the only method in the class, no idea of its name other than 'func_74935_a'). If tree generation (the tree trunks' solid blocks) affects average level calculation, this could explain why I can not reproduce it (trees are different for each try; WTB a way to enforce everything to use the given seed).
If that (or something related) is found out to be the reason, perhaps the StructureStart-object should not only store the bounding box (which can even change as different parts are generated), but also the initially chosen elevation for the structure, and each generated part would then use that stored elevation instead of recalculating it and getting possibly different results.