With digital printers, calibration and the maintenance are very important. Digital printers as any other printers can also use Curves that adjust the colors. There's also settings to change a k100 to a predetermined rich black or overprint setting. Finally, temperature of the room where the printer is, temperature of the printer itself, the stock used and the humidity can change the way the toner will be applied! For example, a lot of Xerox will print more reddish when they are not fully warmed-up and this can happen more often in small print shops that don't receive a lot of orders.
What you are describing seems to be related to the machine calibration and settings; in this case, it's possible the staff has no clue (or does not care) about the issue you're describing. If you don't have any magenta in your black recipe, sent a CMYK file and you see some magenta on your prints then you might need to find a printer that has better quality standards. My guess is your printer doesn't calibrate the machine very often or he's using some "auto-pilot" setting that enriches your black. Some digital printers need to be calibrated between every run, otherwise this should be done at least once a day.
Maybe you could also ask if your files were converted; you're not mentioning anything about the file format you provided. Pdf/x or native files can be problematic for some older rip.
The printer might not understand what you mean by spillage because this word could be more appropriate when speaking of inks or liquids, but you can always mention you see some magenta toner or halo in/around your pure black. Digital printers usually use powders that are cooked.
One thing to keep in mind... digital print-shops and their operators are often the least experienced kind of staff and the lowest quality of all kind of printers. You can't go too crazy about top quality. It's also very common practice for them to rent their equipment, and because of this, they do not maintain their printers well or do not know their equipment. If you use the services of a print-shop that only does digital printing, it's possible you will never get the maximum quality these machines are capable of. My suggestion is to use an offset printer who also does digital printing, and make sure they have recent digital printers.