[Evolution] Message to inbox=NOT! (was :HELO response error)

[Torgny Rasmark <Torgny Rasmark svenska gu se>]

Whenever I send a message I get the following error:
Error while sending '[subjectline]'
HELO response error: Command not implemented: non-fatal

Then the composition window returns. When I close it I'm warned that :
"This message has not been sent.
Do you whish to save your changes?"

This is an error in itself since the message IS sent but somehow
Evolution believes its own lies since the message doesn't show up in the
SENT-folder.

Has the HELO error got something to do with the mailserver not
understanding commands from Evolution or what is going on here. Is this
fixable?

/Torgny