When you changed it. To use your own words, if you "suspect someone is using my services to break the law or engage in terrorism" and you then delete all evidence then you are absolutely tampering with evidence. If AWS was used to DDoS all hospitals in the US and people died, would you see a move by Amazon to delete all trace as just fine and dandy "because the US isn't a police state"? I doubt that. It doesn't matter if it is a small or big crime; knowingly deleting evidence is a crime too.