So there ought to be a setting somewhere that allows or blocks open relaying. It needs fixing. This is one of the big reasons we have spam: because people without a clue set up a mail server for anyone out there to find and use.

Any idea what logs exactly should I check for these varied connections from diverse IPs?
As I know the server is not open relay or anything. Also there aren't other sites hosted on the server. Just our own site which is highly unlikely to have any vulnerability or code as it's just a two page site.

About 50 people have their mail account on this server and I think you are right their credentials might have been compromised.
I could tell all these to change their passwords but I want to find out who exactly has been compromised.

Did you get any results yet?

Security is a Process, not a package.
I would just implement Plesk Mass Password Reset Script and call it "Ongoing Security"
or "Routine Security".

If it continues to happen after resetting ALL passwords, then I'd investigate individual accounts to find a repeat offender.
Chances are someone has never changed an easily-guessed or stolen-by-malware account information.

See also, Parallels Plesk Panel security best practices

Your first line of defense, IMO should be http://kb.parallels.com

1 members found this post helpful.

This is an easy thing to check: http://mxtoolbox.com/diagnostic.aspx

Additional advice...
Start by changing your password(s).

1 members found this post helpful.