Today I generated several worlds with different seeds using server version 1.7. I noticed that a village or other structures are generated approximately every 150 to 200 blocks.
In my opinion, this is far too much. Finding a village should be rare to very rare.

On the technical side: I deleted the world folder, set a new seed and then restarted the server.