I had a similar email hijacking on a hotmail account. I exported my address book to a csv, then deleted all contacts from the account. No more problems. I didn't want to deactivate the account unless unavoidable since it's the one I use to register at various sites.

I opened a gmail account and imported the contacts. I like to use the export-to-csv method to clean out and update my contacts every so periodically due to old addresses, people I don't correspond with, etc.