my AWS account (I use AWS SES to send emails) was recently hacked and used for spam. I managed to fix the issue, but right now I can not send any emails to users who have Gmail accounts, they all go to spam. I contacted AWS support, but they recommended contacting Gmail to ask them to unlock your account. When I contacted Gmail they asked me to contact AWS. I am stuck now in an infinite loop. I thought it was a typical use case and it should be possible to contact any providers to prove that your account is not longer used for spam or it should be done automatically at all.
I think there must be also an algorithm on Google's side that automatically decides whether an email is used for spam or not, but it probably takes time to validate my email again, not sure. But, anyway, is there a way to solve this issue? Please advise.
Allow me to explain that the resolution for this concern is a gradual process wherein you'll need to make your domain trusted on Gmail's server once more if you've been able to send emails to them before.
Now, you're actually correct in this statement:
I think there must be also an algorithm on Google's side that automatically decides whether an email is used for spam or not, but it probably takes time to validate my email again, not sure.
One of the things that Google is checking is a domain's reputation. From the looks of it, that got impacted when the issue happened. I would recommend checking this article out if you have not done so yet. Prevent mail to Gmail users from being blocked or sent to spam. Things like adding SPF and DKIM for your domain would help out in this matter. Note: DMARC is an optional DNS record but I would recommend that you also add it because of what happened.
You can use things like the Postmaster Tools of Google (Get started with Postmaster Tools) or MxToolbox to check the status of your domain and make sure that your DNS records on it are set up correctly.
If you are looking for an immediate fix now, what I can recommend is to have your recipients that use Gmail whitelist your domain using filters. Create rules to filter your emails. To make it easier for them, you can give them an exported filter that has your domain or email address set to "Never send it to Spam" for them to import.
I hope this information helps!