I currently have visited 729 streets. I'm trying to get World-Class Traveler. The most streets visited is 766. I've visited every street listed in the encyclopedia using the Glitch Location Helper. What streets are not listed in the list of Locations?
This might be of use to you:
Several of them don't appear to show up in the encyclopedia.
There's an active thread on the forum discussing the various locations: