I have a physical address that consists of a number and street name. I am "in the country". Like I said - the fire dept could find my house (I actually went to the station and had them pull it up on their computer) but for some reason the street don't show up on the "for public use sites". I've contacted 2 different web sites that say they deal with gettting maps updated but it has been 4 years now and my street still don't exist. All I get from these sites are -"be patient".
Guess I'm wandering a little from the original topic here, but since it's come up...
A couple of the major providers of map data are Navteq and Tele Atlas. Both of them have web pages for reporting map inaccuracies. Don't know if these are the ones you tried, but...if you're bored someday, it might be a fun exercise.
The navteq page is
http://mapreporter.navteq.com/dur-web-external/ and the Tele Atlas page is
http://mapinsight.teleatlas.com/mapfeedback/index.php. My personal experience is with Navteq, which supplies the map data for my Magellan GPS unit. I noticed a couple of errors in routing around my home (the most egregious being that it always wants me to turn onto this street that is actually an overhead bridge that doesn't even intersect with my road) and I reported them on the Navteq page. I figured that the reports would fall into a corporate black hole, never to be seen again...but, lo and behold, about 4 months later, I got two email messages saying something like "the errors you reported have been corrected and will be implemented in the next release of our map data." So...it CAN work, I guess, although this was for Los Angeles, and urban reports might take higher priority than rural ones. I don't know much about how the online map services (Google, Yahoo, etc) work, although I noticed a Google Maps page that said "map data by Tele Atlas." Anyway, might be worth a try.