You mention that you geocoded a list of addresses. What data did you match against? Is it your own? Is it from a reputable source?
If you add the company address points to the street data you'll use to create your network dataset, what sort of precision do they have compared to your points? That is, which points fall in the intersections as they should?
That should just about do it....