SMTP Error Message - What exactly does it mean?

Some people trying to send me mail, receive this message:

##########################################################

This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of its recipients. This is a permanent error. The following address(es) failed:

  klaus@fleischer.it
    SMTP error from remote mail server after RCPT TO:<klaus@fleischer.it>:
    host mx1.netim.net [91.121.137.63]: 554 5.7.1 <klaus@fleischer.it>:
    Relay access denied



##########################################################

And from another address:


##########################################################
> Hi. This is the qmail-send program at mail.gmx.net.
> I'm afraid I wasn't able to deliver your message to the following
> addresses.
> This is a permanent error; I've given up. Sorry it didn't work out.
>
> <klaus@fleischer.it>:
> 91.121.137.63_does_not_like_recipient./Remote_host_said:_554_5.7.1_<klaus@fleischer.it>:_Relay_access_denied/Giving_up_on_91.121.137.63./
>
> --- Below this line is a copy of the message.

##########################################################

Can you tell me, what exactly this means?
Who can resolve this issue?
The hosting provider of the sender or my hosting provider (netim)?

My provider says, this is a problem on the other side, which they can't do anything about.

TIA