I believe that mordi's answer is correct, a zone has a set number of items in it, then it will be depleted. So a fresh zone that has never been visited is a better place to auto-search than one that has had a lot of people in it, even if neither of them is depleted yet.
The search tower adds some items to depleted zones, making them undepleted again. However, the number of items added seems to be significantly smaller than what a fresh zone has.
Building depletion is separate from zone depletion. You can still find items in a building if the containing zone is depleted. Each person can only search a building once per day. You will know when the building is depleted because you will get a message when you search it that says you are sure there is nothing else left.
The search tower undepletes buildings separately from the zone containing it, so you should always try to search buildings even if they were depleted previously and the surrounding zone is depleted.
As a bonus tip, our town has started using the "Uncleared zone" marker to indicate zones that are not depleted. This marker is useless normally (since you can see that there is an unidentified building anyways), but it helps to distinguish a zone that someone has verified is not depleted, versus a zone with no marker which might be depleted and someone forgot to mark it as such. Of course you still have to rely on people changing the uncleared marker when they deplete the zone.