Leaving aside the obviously deficient sysadmin work here: the timeline of the story doesn't add up. I can only hope this explanation is not accurate.

You find notes in your AWS control panel saying you should contact some Hotmail address. OK. So the first thing you do is reach out to that address and take the time to communicate intricate extortion details? Only after that you think maybe it's a good idea to start changing passwords, and right then the other party takes action and deletes all the things?

If that's what actually happened then I'm afraid something like this was bound to happen sooner or later.