End Cities not generating

As well as the Ender Dragon respawning almost every time I re-enter the end (and producing a new egg), and the gateways just taking me back to spawn, I have walked out over 12,000 blocks in one direction and over 3,000 blocks in another direction and found no evidence of any End cities or ships. Strangely, between about 7,000 - 11,000 blocks out, End gateways appear all over the place.