This is a bit alarmist. GV messages appear in search results when 1) you explicitly make them public, and 2) publish the public URL on a public website that Google already indexes.

Google was not randomly making every GV voicemail transcript available in Google Search.

Agreed.. they've blogged about it: http://googlevoiceblog.blogspot.com/2009/10/about-voicemail-...

Conclusion: If you want to search for google voice messages, you will have to use Bing.

Also: If you publish something on the Internet, it might appear on the Internet.

Exactly. This isn't talking about a security hole where private messages appeared in search results. Users posted message transcripts on third party sites where, of course, they got indexed.