The Player's Handbook on Spot says
The Dungeon Master may call for Spot checks to determine the distance at which an encounter begins. A penalty applies on such checks, depending on the distance between the two individuals or groups, and an additional penalty may apply if the character making the Spot check is distracted (not concentrating on being observant).
CONDITION PENALTY
Per 10 feet of distance –1
Spotter distracted –5
Thus the Player's Handbook says the DM may be skipping all this encounter distance jazz and may have encounters just start when he says they start.
But the Dungeon Master's Guide says the DM either makes up the distance between the groups (22-3) or uses the guidelines provided by each terrain's stealth and detection entry (86-93).
While the DMG isn't as explicit as it should be in defining the Listen and Spot skill check DCs necessary for one creature to notice another creature in the wilderness, when I DM those Listen and Spot skill check DCs are 0 but the skill check's result is modified for range, terrain, and other circumstance.
For example, Stealth and Detection in a Forest says
In a sparse forest, the maximum distance at which a Spot check for detecting the nearby presence of others can succeed is 3d6×10 feet. In a medium forest, this distance is 2d8×10 feet, and in a dense forest it is 2d6×10 feet.
Because any square with undergrowth provides concealment, it’s usually easy for a creature to use the Hide skill in the forest. Logs and massive trees provide cover, which also makes hiding possible.
The background noise in the forest makes Listen checks more difficult, increasing the DC of the check by 2 per 10 feet, not 1 (but note that Move Silently is also more difficult in undergrowth). (87)
Hence, when I DM, the Listen and Spot skill check DCs necessary to successfully notice, for example, a creature 110 ft. in a sparse forest are 0, but the creature trying to do so suffers a −22 penalty on its Listen skill check and a −11 penalty on its Spot skill check. (It's also reasonable to adjust the Spot check's result based on the creature's size modifier.)
Technically, I think once encounter distance is established, both sides continue making new Listen and Spot skill checks each round. This is tedious, and when I DM if neither side is aware of the other and either side is moving away from the other I allow the encounter to end, often the PCs and players none the wiser. However, if neither side is aware of each other and either side is moving toward the other, I have all involved make checks each round.
Later supplements expand the DMG's terrains (for example, Stormwrack includes terrains from ice floes to a ship's deck (14-21)).
Note Dungeons and Dragons, Third Edition encounter distances were fairly stable with simple but easily adjudicated variations. The Dungeons and Dragons 3.5 revision makes encounter distances more complicated and eliminates, for example, random dungeon and urban encounter distances, relying instead on the DM to fairly generate those distances on the fly. (For more on Dungeons and Dragons, Third Edition encounter distances, see this answer.)
