I'd go and check the fees of several banks (Preis- und Leistungsverzeichnis) since they vary substantially.
I checked a few right now, and there is no indication of any such new regulation. One list contains a reminder that for foreign checks above 12.5 k€ you have some reporting duties for foreign trade statistics (but that is nothing new).
I'd also go back to Deutsche Bank and try again and if they don't take it, insist on them showing you exactly why they refuse (what regulation).
The Preis- und Leistungsverzeichnis of the Deutsche Bank for private customers does list fees for depositing foreign bank/foreign currency checks. There is indication that they have 2 modes, one where the value appears immediately on your acount but you cannot access that money until they actually got the money from the other bank, and one where the money appears on your account only after they actually got it from the other bank. The second mode is even more expensive (foreign check deposit fee 25 € or 0.15 % of the value, whatever is higher, postage fee 3,10 € plus any other fees they encounter) than the first, and for US$ only the second mode is available.
For business customers, prices may be different (and typically not lower). Also, I'm not sure whether a bank could have a service contract with you that excludes handling of checks - I wouldn't exclude this possibility. But that would be their service conditions rather than regulation or law.