SQL Server 2005 Database Mail Command Not Supported (502) SMTP Error

Hi all,

At this moment I'm trying to get database mail working. According to
some people it should be easy. Well...that is not the case for me.
I'm having the following error:

The mail could not be sent to the recipients because of the mail server
failure. (Sending Mail using Account 2 (2006-11-24T08:48:15). Exception
Message: Cannot send mails to mail server. (Command not implemented.
The server response was: Command not Supported).
)

SQL Server 2005 is installed on a separate server and the SMTP Server
is Lotus Notes. connecting with port 25.

Start and stopping the SQL Server and SQL Server agent i tried already.
i tried sysmail_stop_sp and sysmail_start_sp.

Sometimes when starting or stopping the Mail with the following
commands :

exec sysmail_stop_sp
GO

exec sysmail_start_sp
GO

I will get the following error:

Msg 233, Level 20, State 0, Line 0
A transport-level error has occurred when sending the request to the
server. (provider: Shared Memory Provider, error: 0 - No process is on
the other end of the pipe.)

So any help would be appreciated.

Hennie