We have a shared hosting service running QMail and Plesk. One of our inactive clients was left active in the system by mistake, and spammers found their very weak passwords and sent out a massive barrage of messages before we caught the problem and shut off the services for that domain.

My question is this: How did they get access to that domain in the first place? The client is long-gone and the domain/DNS is not pointing at our server at all, and neither is the MX record. So how were they able to find that domain and exploit it when nothing on the "outside" was pointing to it?