User choice.
The argument about it being user choice is crap.
For starters, Google Toolbar is bundled with so many different things these days that you have to make a concerted effort *not* to have it installed. We, as computer savvy users are aware that you have to watch install apps for the sneaky "Would you also like..." bit but most aren't and will just "I agree > Next > Next > Finish" their way through the setup.
Secondly, even if they do pay attention during setup, the majority of users don't understand what a 404 is, let alone what it's there for (more important than letting them know they/the site has made a whoopsie is providing suggestions on what to do about it). So when Google ask if they'd like to take the nasty errors away, of course they're gonna say yes.
Third, Google don't do anything which isn't about their bottom line in the end. Making money by inserting a handy search box in response to user typos or (heaven forbid) my balls up is not exactly wrong but still pisses me off a great deal. The argument that not very many sites should/do have <512b error pages is bunk too - if it was an insignificant proportion, they wouldn't waste their effort with this scheme.
Finally, the site I run is someone's small-scale livelihood. Like I said way up there, if someone goes off-piste, I need to help them out with getting back to the right place such that they may still make a purchase. If they're presented with a search box already populated with keywords from what they were looking for, the chances are the results of the search will simply redirect them to a bigger fish with a higher mystical PageRank and the customer will be lost.
<Farnsworth> If anyone wants me, I'll be in the Angry Dome </Farnsworth>