This problem exists due to very long polylines. Geocoding doesn't not handle such long polylines that contain more than 256 points. The workaround is to generalize the lines. Users can use the GP Simply Line tool under Data Management tools -> Generalization or the Smooth Curve or Line tool from the Advanced Editing toolbar on the line feature. Then rebuild the address locator.