Possible Compromised Server

There's a few ways.

One way is to perform an nmap scan on your server to see which ports are open.  You'll also want to see if your server is listed in any spam databases.  Go to:  http://www.dnsbl.info/ and type in the public IP of your mail server.  

You'll also want to check, immediately, which accounts have membership in ANY of your admin groups, and verify that they are supposed to be there.  Then, reset the passwords for those accounts and ensure you follow good password practices.  

Beyond that, also make sure you've got good, up to date anti-virus installed on the server, and run it.

If accounts are being created and you are sure it was no other admin, your server is compromised, period. Restore it from a clean backup. I would not trust anything else.

The server sounds compromised; probably one or more of your clients aswell. I will assume that you have a up-to-date anti-virus and firewall enabled on the server; which means that the backdoor or whatever came via one of the clients.

Save data on the server, scan it offline, reinstall from scratch. keep all clients offline. Then offline-scan your clients to determine the source and then connect clients and server to the network.

There is no need to reinstall, fix, scan before you know what happend and how; but to determine this keep the system offline (not on net) to prevent further damage to systems and data.

Are you the only person maintaining this server? Some of my clients install application servers on their SBS and the application support people usually get the password out of them and start creating user accounts etc. Maybe you should check with your client who has access to the password or at the very least change it regularly.
Regarding not being able to send email to certain domains. This could mean somehow the mail server has been blacklisted. This happens when spam gets sent from the server to one of many many trap-mailboxes out there or when enough people have been reported as spamming from the mail server. If you are sure nobody is spamming from your mail server you can go here to test if your mail server has been blacklisted. Just put in your client's real ip address and hit enter. If you're not sure what the ip is log on to the server's console and visit this website. If you are blacklisted the good people who ran the test for you also offer to help getting you unlisted on their website.
Let me know if this helps. :)