> It bothers me a lot when services, such as Google Voice, announce to all parties that such recording is occurring.
Google is based in California. There is a good probability that the act of recording occurs there. California is an all-party consent state. Also, even if the recording isn't happening in California, it's potentially tricky to be sure that no party to the call is in California (even numbers assigned to landlines don't assure that the person ultimately connecting is in a particular place.)