Are you using ARS, or just directly accessing a trunk group for outbound calls? This sounds like an ARS issue not modifying the digit string correctly, or inconsistency between extensions where some are using ARS and others direct trunk group access.
Verify first each trunk, during a slow time dial each trunk's ext number individually and make a variety of calls (local, long dist, toll free, etc), this will verify the trunks themselves are good. Then check your ARS routing and make sure the configuration matches your local dialing format (7, 10, 1+10 , etc) and the facility groups contain the correct trunk groups. If you are accessing the trunk group directly, make sure it is consistent through out the system.