Big problem with mails

Any help for this:

Today all of our clients (almost) called and told us that they can't send mails out.

The get following message:

Host xxx.xxx.xxx.xxx is not permitted to relay through server.xxxxxx.xxx.
Perhahps you have not logged into the pop/imap server the last 30 minutes.
You may also have been rejected because your ip addr.


We did not change anything - we only made the recommended security update.

Any help would be great!
Thanks!!

Seven