I've done three long road trips this summer, and, yes, this can be a problem. Finding the Superchargers can be difficult, especially in large, busy shopping centers, but in other places as well.
I've learned to prepare. When driving an ICE you can usually be confident that if you pull off at an exit, you will find a gas station somewhere. With a Tesla you need to know ahead of time which Supercharges you will likely be using. Of course the nave system in the car will tell you that. But it helps to do some research beyond that. The nav system will sometimes direct you precisely to the Superchargers, but other times only get you to the near vicinity. And sometimes it is wrong. It's not enough to know it's in the XYZ shopping center; you also have to know it's behind the ABC store on the west side of the lower lot. Study the locations on the Tesla website, Google maps, etc. And, as you mentioned, Plugshare and other sites have photos that can help you find the right spot. Usually it's not a problem. Hotel and restaurant parking lots are generally not very big, and you can often spot the Superchargers from the road as you drive up. At other times, it's a real challenge and it helps if you prepare ahead of time.