Taking network segmentation into consideration how do I define the scope of which passwords to reset in the event of a breach?
Change all your passwords for all accounts on all computers that are on the same network as the compromised systems. No really. All accounts. All computers. Yes, you're right, this might be overkill; on the other hand, it might not.
Background:
While working on writing an incident response plan for my day job I referred to How do I deal with a compromised server? for some ideas as to what should take place when. I am working with a segmented network as defined using the PCI DSS Scoping Toolkit. My setup involves both non domain and a domain with internal segmentation applied.
I would interpret that as all networks connected to the location where the incursion occurred, are under your administrative control, and that are connected by ip connectivity. IP connectivity either means unrestricted, or allowed by a firewall rule. Essentially, any possible network where the attacker could pivot to/from.
I'd suggest two areas to look at, depending on your level of sensitivity (I originally wrote "paranoia" there, but I think there's a valid point to be made about scaling your level of response vs. the consequences for not doing enough).
I'd personally consider any Windows AD domain(* other centralised account management services are available, assume I'm talking about them too) that the victim was connected to as suspect. While they are less prevalent these days there have been attacks in the past using captured 'domain user' account to authenticate to the domain and act as a starting point for compromising domain admin accounts.
The other area I'd worry about is where you might have a system that's outside of your centralised authentication mechanism, but where a user has re-used account details. Once you have a username/password combo gathered from one source its fairly trivial to play that combo back to every other system you can find to see if it works.
Lastly, don't forget about any systems the compromised server connects to using credentials buried in the code itself (e.g. database connections, etc).
If you're working to the definition of segmentation used in the scoping toolkit, e.g. total isolation then you can be reasonably sure that the attack hasn't crossed those boundaries. That's actually a good place to start from. In a lot of ways, by working on this ahead of a problem, you're already very far ahead in the game - I wrote the question you reference as a guide for people who haven't planned that far ahead.