what would you check, which is your recommendation?

Are the emails "bounced"?

Really, this is not an "infection". Spammers grab random domains at times and start their work. Random user names are attached to the domain and spam is sent. They don't actually need to have access to any server or DNS.

Of course, it is quite a bit more complicated, but if it is "bounced", meaning that you are being used for the send (both from and to), the you can intercept at the domain level/server level (assuming you have an exchange server).

What you should be doing is reacting: delete and intercept the bounces and contact an attorney to track down and pursue legal action if desired. Your nightmare is just beginning. If you have a company site, this site could possibly become blacklisted by the mail servers and everthing will go to "Junk" when you send.

Lastly, if you feel that someone has a compromised address book, then you need to root deep into the actual client station, but this seems unlikely even from your broad description.

First and foremost, I would go straight to the server and start intercepting. Black list at that level so that users remain mostly uneffected.