Some ideas for controlling search engines:
Deleted blogs' robots.txt
All deleted blogs should have their robots.txt set to Disallow: /
Stop wp-login.php from being indexed by adding <meta name="robots" content="noindex" />
An option to disable archiving by search engines by adding <meta name="robots" content="noarchive" /> and Disallow the ia_archiver robot.
An option to disable pings to ping servers (such as weblogs.com.)
An option to disable feeds should help to keep out some bots, (although it's quite a sacrifice.)