I've done larger engagements in a week, and I've been with a partner for about the same size of engagement over a week as well. It really comes down to how much you want to spend to obtain reasonable assurance that your network is secure.
Three things to keep in mind: First, every system doesn't need to be tested. Your 2000 user workstations are likely nearly identical. You probably have a mix of fully-patched Windows XP and 7 systems running default services. That there just took a large number down to two. I would focus on systems that deviate from the norm. Did a developer install Tomcat and SQL Server and not bother to even change default credentials? Are there open shares? An so on. That type of information is easy to relatively quickly across a large number of systems. It would be a different matter if each system had something odd like that, but that would be quite a rare occurrence. That'll be true to a lesser extent on the server side as well. If you have 20 domain controllers scatter across all your sites, there probably isn't much value in testing each one if they're configured the same. However, the one that's also running a web server or is a couple service packs behind may be interesting...
Sure, one system could have a local admin using admin/admin credentials, but unless you find something like null session enumeration available, to even determine what local accounts are present, you can spend an infinite amount of time testing what-if scenarios like that. Activities like that are better left to internal audits anyway. Use Powershell to obtain and compare local accounts across your systems and address any abnormalities. Done. There's no value in paying someone to sit and watch Hydra run at random.
Second, it's not a pen tester's job to enumerate every vulnerability on every system. I can usually get a feel for how the engagement is going to go in the first day or two (if not immediately in some unfortunate cases). If I review 10% of your assets and notice rampant patching problems, default credentials, etc., those issues likely extend to the rest of your assets as well. It's easy enough to stop there and say, "Hey, you have serious deficiencies in x, y, and z. Address those and we'll try this again when you're in a better place." It's an iterative process and things are always changing. The important thing is to determine procedural deficiencies and correct them so they don't continue to plague an organization.
Finally, be prepared for the engagement whenever you do it. There is absolutely no reason I should still be finding MS08-067 or unknown NT4 systems. Correct low-hanging fruit, such as ARP and NBNS spoofing attacks, in advance. The better position you're in, the more value you'll get. If you don't currently do vulnerability management, at least pick up a copy of Nessus and do some scanning and remediation yourself. Similarly, be sure to vet prospective vendors and be confident you're hiring someone qualified, or you may get nothing more than a repackaged Nessus scan.
The day you stop learning is the day you start becoming obsolete.