The number one reason for not finding paths to all the destinations is network connectivity or some restriction that is causing the network to be disconnected. You can check if the network is connected in a couple of ways:
1. Use the Network Identify tool. It is on the Network Analyst toolbar. Second icon from the right. Activate it and then click on a network edge. It will pop up a list of the attributes of that edge and the edges and junctions it is connected to. Is it returning what you expect? Are any restriction attributes set that will cause the edge to be not traversed?
2. Use the Service Area solver. Load one of your origins from OD as a facility. Bring up the properties of SA layer and on the Analysis settings tab set a break value of, say, 10 minutes (if using time). On the Polygon Generation tab, turn off the polygons. On the Line Generation tab, turn on the generate lines. Close the properties and solve the service area layer. This should draw all the lines connected to that origin within 10 minutes. Do you see what you think you should see Or is there disconnects in the network?
So if you do see disconnect, one potential thing to watch out for is the connectivity setting of the network dataset. Is this data supposed to connect at each edge end point OR is it supposed to connect to any vertices along an edge (yes if you got the data from a source like open streetmap). In that case you could switch the connectivity policy to Any vertex and rebuild the network. After a re-build of a network, make sure to, in the NA window, right-click the Origins and Destinations and recalculate location fields before you solve the layer again.
Jay Sandhu