Generally if your email is blacklisted there are 2 things you can do each time this happens.
- It's temporarily black listed and will be lifted after about 24-48 hours (depends on black list) after the last spam was reported.
- you contact the blacklist site and request they remove your email from their blacklist.
It is harder to figure out what blacklist the other email provider uses, but in some cases they have it listed on their website in cases like that. Instead, go to a website like http://mxtoolbox.com/blacklists.aspx to search if your domain is on a blacklist. There are multiple sites out there that can check, but that's just one of them (https://www.google.com/search?q=email+blacklist).
If you use
email@example.com, then use
mydomain.com to find out if it's blacklisted. Generally you will get at least 1 hit that you are on a blacklist, but if you are patient it will become unlisted.
So besides the 2 options i listed above as far as getting it off of the blacklist, there's 2 more options you have to prevent it from happening again. These 2 are separate because you only have to do them once, or in rare situations (i.e. email account gets compromised).
- Make sure you do not have an easy to guess password, and make sure it's unique to your email. Stolen passwords can be used (no matter how rare it happens) to break into your email, bank account, etc.
- Setup an SPF (Sender Policy Framework) record on your domain. This is a DNS record that just states which servers are allowed to send email through your domain.
Think of an SPF record as a sort of seal that states your server is legitimate, while the others are fake. Keep in mind, not every server/provider checks the SPF record and can still report your email domain as spam.
Sadly there isn't much you can do beyond that, but it is usually fixed by waiting it out or requesting a black list to remove your domain.
Edit: I should point out in your case, you didn't put anything about your email, so this is under the assumption you are not using an email like @yahoo.com or @gmail.com. It doesn't change much even if you are, but just pointing out that I am assuming you have control over your domain.