From the rule book:
When one or more abilities have the same timing trigger or
can be triggered at the same time, each player chooses the
order his own abilities trigger. A player can trigger an optional
conditional ability before a required conditional ability if they
both have the same trigger condition.
If players ever want to perform simultaneous effects at the same
time, the player whose turn it is resolves all of his effects first.
So the question becomes, are "encounters" and "encountered" considered the same trigger, for all intents and purposes?
The rule book breaks the "Confrontation Phase" down into "Approaching" and "Encountering" ICE, but encountering is not broken down any further. Taking the rule book at face-value here seems to imply that all "Encounter" related triggers happen simultaneously.
Therefore, the active player (the Runner) gets to resolve all of their triggered effects first, and then the other player gets to resolve theirs.
The thing is that Parasite triggers off a new condition caused by the effects being triggered as a result of the encounter, so I would assume you need to resolve all of the current effects before Parasite can resolve its trigger, since the original effects were technically simultaneous.
So, taking all that into account, I would say that the Runner needs to pay the 3* or the run will end.
Furthermore, if the Runner does not pay the 3* for Tollbooth, I'm not even sure that Tollbooth would be trashed at all. Technically, Tollbooth's triggered effect ends the run, which ends the encounter, which ends the effects from Ice Carver, removing the condition that would cause Parasite to trash it. However, the condition for parasite did exist briefly, so does that mean that its effect is already triggered and queued up, or is only triggered once all current simultaneous triggers are resolved?
With regard to this point, I have to lean towards Parasite being forced to wait until all of the simultaneous triggers resolve before being triggered itself and therefore not actually being able to destroy Tollbooth since without the effects of Ice Carver.
Obviously, if the runner pays the toll, Tollbooth would be toast.
One final note here, I use Ice Carver in my example because both it and Tollbooth are automatically triggered by the encounter. The Datasucker, on the other hand, has a paid ability that can be used during an encounter. If you were to only have the Datasucker and not the Ice Carver, I would say that the Tollbooth definitely triggers first because it happens automatically whereas the Datasucker can be activated once a certain condition exists but doesn't trigger as a result of that condition.
**Edit** I just noticed Brad's response and we're almost on the same page, except that I'm not sure if I agree that Ice Carver is a constant effect. If it was, I would expect it to read "All ICE has -1 strength" or "All installed (or rezzed) ICE has -1 strength".
Parasite, however, is definitely a constant effect (forgot to double check the actual wording of that one before posting…) but I'm still not sure how it interacts with Tollbooth's effect which, in my scenario above, has technically already triggered before the trash condition was met. Can you trash a card that has been triggered before the trigger is resolved? If so, what happens to the triggered effect? Does it still resolve or does it "fizzle"?