Well, the big 2 content providers are Teleatlas and Navteq. I'm sure you could find problems with both of them... just in these cases, it's problems with Navteq. If you take a look on the web though, there are also people complaining about Teleatlas.
These days as well as asking for the street name I also tend to ask for the nearest connecting street, just in case.