Fortunately I have found a quick solution to this problem, which I have been using for over a year. After copying your text in Safari, simply change focus to the Google search bar (Command-Option-F) or URL bar (Command-L), then execute Paste, Select All, and finally Cut. This can be done very quickly from the keyboard by holding Command and typing V-A-X, so this doesn't take a significant amount of time once you get used to it. Then end result is text with no formatting.
This still seems to work reliably even with huge amounts of text: I tried to paste pi to the millionth digit into the Google search bar as a test. Text selection within the bar became dreadfully slow, but when I cut it and then pasted it into TextEdit, all of the text came through properly, with all of the formatting stripped.
[robg adds: You might also look for a 'Paste and Match Style' option in the destination program. If it exists, this usually has the keyboard shortcut of Shift-Command-Option-V. But for apps that insist on pasting with style, this is a pretty quick workaround.]

