For example, I live in a "single party" state. I can record any conversation I'm involved in, without informing the other party, even if the other party is located in a state that requires two party consent.
BTW, murder isn't a violation of a federal law here either, except under versy specific circumstances (the victim is a federal employee on official business, etc.)
However, under the FCC's interpretation of US federal wiretap law, consent doesn't matter at all if the conversation never hits the public switched telephone network.
Also, you might want to reconsider that the statement about "they would have found zero logs and zero evidence and pristine servers". Unless you're doing monitoring and logging on a machine that is passive and completely sub rosa, and done via a passive tap, such evidence is actually very hard to get rid off. Just think of about all those little files that are getting backed up every night. Unless of course, you're not doing backups, but then you have other problems.
Stop the TSA now! Boycott the airlines.