usually it helps since sezrchup.de should have an interest in their reputation.
Gee i almost wish the porn spammer on my links2 installation would be so easy to stop)
webmaster@selfmaster.de
seems to be their contact address (but you can try soft.de as well or any other you find on their site.

Here is the german text (in short) (please suply with your Search Engine Name and your name where stated) you can use to advice them of the fact that they are not autorized to auto submit unless they have written consensus with you.

Werte searchup Leute,
euer auto submission service at http://www.searchup.de/promo-ten/maschinen.html
benutzt leider unsere Search Engine "Name of it here" OHNE ERFRAGTE ERLAUBNIS!
Da wir den spam nicht listen oder behandeln koennen erwarten wir dass Ihr unsere S.E. SOFORT aus euerer Liste entfernen, andernfalls sehen wir uns gezwungen rechtliche schritte gegen Euch zu unternehmen.
Freundlichst
"your name here"

Hope that will get the Attention of them.
As for my own spam problem, if anyone has a receipe to stop spamming in general, i would like to hear of it.
Rudolf