(this was intended to be a reply to your comment under Massimo's answer, however, it grew past the character limit)
"Not knowing" who is sending them is simply irresponsible. By providing a service, you now are expected to protect Internet from your users misusing the service.
You are providing service, you are now in charge of what your users do. The service allows your users "anonymously" do stuff in the Internet; it's anonymous for them because they just do things under your name, and you chose to not record who does who.
So your name is the one known to blame. You were blamed for wrongdoings in the Internet; maybe, it's some of your users is doing something nasty, but nobody cares, it's now your problem because it's your service. For me (e.g. if I was the victim of that wrongdoings), it's Hetzner's IP address what is recorded, therefore it's Hetzner who is responsible. Hetzner knows to whom they lent this IP, it's you, so they pass this responsibility further to you. Now it's your turn to respond.
So, either you'll need to find out who is doing wrong and timely react, and, probably, even prevent this proactively in the future, or Hetzner will stop providing a service to you in turn, because this is the best thing they can do so your (or, your user's, nobody cares, because their contract is with you, not with your users) actions don't hurt their reputation.
Install at least the traffic flow recording tools, software like flow-tools. Forbid exiting to port 25 to prevent spamming; normal email sending won't be affected.
