Hello, Fiona!
I'd like to clarify, just to make sure we are discussing the same thing. Are you talking about Origins that are unlocated when loading locations? Or are you talking about Origins that find no paths to any destination when solving the analysis? The reason I ask is that most of your post indicates that this is an issue with loading locations, but the "Default Cutoff Value" only applies to solving the analysis.
Also, what network dataset are you using? Is your work being done in ArcMap, or via the geoprocessing tools?
For unlocated origins, maybe you could do some experiments on those origins that did not properly locate. I am assuming that all of this work is being done in ArcMap, and not with the geoprocessing tools. Have you tried turning on (checking) "Exclude restricted portions", just to see if it makes a difference? Have you tried to increase the search tolerance to something clearly excessive?
Also, be sure that "Use Geometry" is selected in the Load Locations dialog. And, be sure that on the Layer Properties dialog on the Network Locations tab, that you have checked on the network sources upon which you wish to locate.
Let me know if any of this helps,
Patrick