It sounds like this is likely a connectivity issue in your network dataset, causing the expected paths to be invalid. You should investigate your connectivity policy in the network dataset properties and also check to make sure that any features you expect to connect to each other actually share a common vertex at the intended connection point (it does not suffice for features merely to touch or cross; they must explicitly share a common vertex at their meeting point in order to establish connection). If this is indeed the case, you can force features that touch to share a common vertex by using the 'Integrate' GP tool.