I think it's illegal in all states if no subject of the recording provides consent, the split is between states with a one-party consent rule and an all-parties consent rule.

In states which require all-party consent, are things like "Hey Siri" illegal?

Seems like you could distinguish between "recording" and "listening" in that case. Then "recording" is only initiated upon the activation of a trigger which confirms two-party consent.

Though I wouldn't be surprised if Apple intermittently recorded background noise for ex. training purposes in violation of that, anyways.

But doesn't agreeing to the ToS mean you agree to be surveilled?

ToS doesn't trump local law!

* By reading this post you give me the right to steal all your underwear

A lot of ToS are null and void in many countries. The paragraphs that are null and void then usually are just void, but the rest of the contract still holds.

It might be the phone of someone else.

You can argue it isn't wiretapping/recording. Like Shazam, they are fingerprinting the audio and sending the fingerprints back to a server. In the same way, something like Moves fingerprints the gyroscope on your phone and identifies if you are running/walking/taking a car -- but this isn't surveillance.