Chunks do not generate deterministically

Chunks do not generate identically when regenerated.

Repeat by:
1. Recreate the same world.

Or:

2. Delete region files, and let them be regenerated.

Landscape is the same. Decorations (trees, plants, mushrooms, etc; sand on the floor of the ocean) are NOT the same.

Easiest way to see this is to look at the region file boundary in the ocean with a potion of night vision. However, I managed to find significant differences in plants near spawn when I re-created a test world.

Additional notes:
1.0 and 1.1: I could, and did, regenerate chunks and worlds without any problem. I thought I did the same in 125 as well.

I can confirm that changes happen in 164 and 174. Not sure about 147 (I know it does not match the 125 generation); did not test the 15x series.