smtpmail.el: Problem with STARTTLS + Authentication

[Felix Natter]

hello,

I currently cannot smtp-authenticate:
220 ux-2s14.inf.fh-bonn-rhein-sieg.de ESMTP Exim 3.12 #1 Mon, 21 Jul 2008 
10:14:52 +0200
250-ux-2s14.inf.fh-bonn-rhein-sieg.de Hello pD9E83FE2.dip.t-dialin.net 
[217.232.63.226], pleased to meet you
250-ENHANCEDSTATUSCODES
250-PIPELINING
250-EXPN
250-8BITMIME
250-SIZE
250-DSN
250-ETRN
250-AUTH LOGIN PLAIN
250-STARTTLS
250-DELIVERBY
250 HELP
250 2.1.0 <felix.natter@smail.inf.fh-brs.de>... Sender ok
250 2.1.5 <marlis.vonderhude@fh-bonn-rhein-sieg.de>... Recipient ok
354 Enter mail, end with "." on a line by itself
554 5.7.1 Your mail has been rated as SPAM, score: 5.8 
(BAYES_50,HELO_LOCALHOST,RCVD_IN_PBL,RCVD_IN_SORBS_DUL,RDNS_DYNAMIC)
221 2.0.0 ux-2s14.inf.fh-bonn-rhein-sieg.de closing connection
smtpmail-send-it: Sending failed; SMTP protocol error

=> the mail is rejected because it's from a dynamic IP *only because I
couldn't authenticate*. Now the helpdesk says that this is missing:
  "AUTH PLAIN $*(%)%$)%" (letztes Token: base64-encoded Nutzer & Pwd)
but I guess this just isn't shown in *Messages*?

This is my setup:

(setq message-send-mail-function 'smtpmail-send-it
      send-mail-function 'smtpmail-send-it
      smtpmail-smtp-server "smtp.inf.fh-bonn-rhein-sieg.de"
      smtpmail-local-domain nil
      smtpmail-debug-info t)
;;Documentation:
;;Specify STARTTLS keys and certificates for servers.
;;This is a list of four-element list with `servername' (a string),
;;`port' (an integer), `key' (a filename) and `certificate' (a filename).
(setq smtpmail-starttls-credentials
      '(("smtp.inf.fh-bonn-rhein-sieg.de" 587 nil nil)))
;; this is still needed, even with STARTTLS
(setq smtpmail-auth-credentials
      '(("smtp.inf.fh-bonn-rhein-sieg.de" 587 "fnatte2s" "<MY PASSWORD>")))

What can I do to fix this? Could it be problems on the other side?

thanks!

-- 
Felix Natter