Short answer: probably not. It may make your brakes harder to set up but that's all.
Dishing is having shorter, tighter spokes on one side of the wheel to move the rim towards that side relative to the midpoint between the flanges (where the spokes attach on the hub). The frame and wheel are still built symmetrically for historical reasons, but dishing allows the flanges to be assymetric so you have more space to fit cogs in.
The bike shop guy is probably right if he used a spoke tensiometer (if he didn't you need to find a better bike shop). There's a limit on how tight the spokes can be, usually set by the rim but sometimes by the hub (or with aluminium spokes, the spokes). If you overtension the spokes something will give way, usually nipples start pulling through your rim.
If he has wound the spokes up as tight as he can and the dishing is still not right, you are indeed stuck. Since it seems to work like that, I say accept it and move on. Expect the wheel to be a little more fragile than before, more likely to buckle and it will fail earlier than it should. But since it should last a lifetime, that doesn't mean it won't last until the braking surface wears away.
If the new rim is the same or only slightly different from the old one it's possible they used the old spokes, but that's penny wise and pound foolish. Spokes stretch slightly and settle into position when the wheel is built for the first time, and trying to do that a second time rarely works well - spokes are more likely to break in the future. Much better to pay the $20 or so for new spokes and be done with it. The wheelbuild labour cost is so much greater than the spoke cost that it's foolish not to just buy new spokes.
One cheat that can give you a millimetre each way is to play with the spacers and locknuts on your axle. There are thin locknuts and fat locknuts, as well as a variety of spacers. With most wheels you can swap bits around to shuffle the whole thing a little bit sideways. This changes the chainline and can mean the chain hits the frame in the smallest cog, so it needs to be done cautiously. But if you are really worried about that last millimetre that should fix it.