Couple of questions. Cross patterns are seen when enlarging: are you viewing the scans on a monitor, generating a digitally enlarged negative or digitally printing the image enlarged?
Assuming the negative is continuous tone with no pattern (check the negs with a loupe on a light box) if they’re smooth, the pattern must be digitally generated. Some people prefer converting 35mm negs using a digital camera with macro lens to avoid the software settings and enhancements of flat bed scanners.
Before asking them to rescan, check the shadows and mid-tones for any other artifacts not present in the negative. It may be a simple negative highlight setting or something more involved if you feel the grain has also been overly sharpened.
good luck