I see 3 problems. The first two are pretty important. The third one isn't.
1) You aren't sparging with enough water. A five gallon batch should start the boil with about 6.5 gallons. Whatever water didn't start in the mash may as well be in the sparge. (unless this is an exceeding light beer. There is a threshold where you can run the sugars in the water too low and start extracting tannins from the grist. That's bad)
2) It sounds like you LHBS needs to adjust their mill.
3) Efficiency doesn't need to be exceptionally high. It just needs to be consistent. I see people tout their efficiency often in these forums, but the truth is that it just needs to be consistent so you can calculate with it. The exception to this is when you have to add so much more grain to your batch that it further decreases you efficiency, making it even more difficult to brew. When this happens, you need to look for more efficient methods.