I prefer Streets and Trips 2004 myself. Voice navigation, voice control and great maps. I was able to locate all of the listed places you had problems with except for frys, that I could not locate by searching.
in n out,ca
the results returned were all of those stores/restaurants in california matching those criteria. I'm actually surprised fry's wasn't there. But something to look into if no one else speaks up about something better.