With permalinks enabled, requests for non-existing URL paths result in a resource intensive select. The problem is that WP::query_posts() doesn't halt execution when WP::parse_request() 404s, causing WP_Query::get_posts() to fetch the x most recent posts. More details: http://maisonbisson.com/blog/post/12035 .
The attached patch simply short-circuits WP::query_posts() if there's a 404. At rboren's suggestion, it also calls WP_Query::parse_query(), as some templates expect it to have run.
Honestly not sure if did_permalink is necessary, but the code works in my environments.