Yesterday I noticed that one of my e-mail addresses (the only one within that domain) started to receive a lot of weird messages that the mail haven't reach the target (something like "Sorry, Qmail wasn't able to deliver..." etc.). I (or rather the hosting provider I have a shared hosting account from) do(es)n't use QMail as far as I know. Further more, in the "From" field within these unsuccessfully delivered returned e-mails I can see different, odd names I have no idea about.
I don't want to put name of the hosting provider publically, and I'm really not into the security subject, but it seems to me like someone somehow got access to the mailing server from my webhosting provider, and started to use it to send a spam messages around the world - I saw english, german and chinese texts, among others there in the messages.
For the moment, I modified DNS of that one mentioned domain, so that it doesn't indicate to my hosting provider's servers (and the webpage is inaccessible either, then).
But what should I do in the situation like this? And what does it actually mean? Is changing a hosting provider sufficient, or hacker still would have access to my mailing account?
Maybe I should remove all the data from the server? What is the chance that he has access to all the other data (e.g. shell, hdd etc.) on the server where I have e.g. my webpages placed?
UPDATE Thanks for suggestions.
So, my provider's technical staff wasn't too interested in the problem, and he said of a number of reasons why someone could be able to use my email address for spamming. He said that there was not security issues (of course, he could have lied - typical commercial practice :P my former boss used it too sometimes :P ) on their side, and suggested that my password could have being stealed by a malware software (I use antivirus, though I really never believed any of the software like that). Hmm.
But now I recall that for almost all my email addresses (different domains) like 3 months ago I started to receieve a weird spam - it was exactly the same message for each of my addresses. Since I register most of my accounts for popular portals like Ebay, Twitter etc., I think now that one of these portals' security could have been broken!
(And why I think that the issue is not connected to my own computer: because all the email addresses that I haven't registered for Twitter etc. accounts, never received any spam - it was like a policy for the email addresses that has been registered. And I didn't register them anywhere else than the popular webportals).
Does anyone know about a case of breaking in to one of popular (particularly social) webportals recently like about, say, 4 months ago?