If the printer is requiring InDesign files and not using PDFs, I'd say you need to look at finding a new printer (assuming it's your choice, of course). If it's client who's requiring InDesign files, then could you send the InDesign file to the client and quietly pass the print PDF directly to the printer?
If you can't replicate the problem on your own computers then you couldn't have foreseen it even if you had checked the IDML before you sent it. Sounds to me like the error is with the printer/client here. They asked for the wrong file, you sent them what they'd asked for and the correct file as well, they didn't check print proofs or compare the IDML output with the PDF. I'd go back to the client and say that it was fine when it left your offices, and it's their responsibility what happened to it after that. (Only I might be a little more polite than that, if I ever wanted to work for them again!)