How can I simplify this WordPress query to increase performance?

I have several boxes in a WordPress site which have to show a selection of posts which belong to certain categories AND ALSO do not belong to several others. Using only native wordpress tools the result is a query like this:

SELECT SQL_CALC_FOUND_ROWS  wp_posts.*
FROM wp_posts
INNER JOIN wp_term_relationships
ON (wp_posts.ID = wp_term_relationships.object_id)
INNER JOIN wp_term_taxonomy
ON (wp_term_relationships.term_taxonomy_id = wp_term_taxonomy.term_taxonomy_id)
WHERE 1=1
AND wp_term_taxonomy.taxonomy = 'category'
AND wp_term_taxonomy.term_id IN ('1', '49')
AND wp_posts.ID NOT IN ( 
    SELECT tr.object_id
    FROM wp_term_relationships AS tr
    INNER JOIN wp_term_taxonomy AS tt
    ON tr.term_taxonomy_id = tt.term_taxonomy_id
    WHERE tt.taxonomy = 'category'
    AND tt.term_id IN ('3394', '49', '794', '183') )
AND wp_posts.post_type = 'post'
AND (wp_posts.post_status = 'publish')
GROUP BY wp_posts.ID
ORDER BY wp_posts.post_date DESC
LIMIT 0, 5;

now this is quite expensive and ends up in the slow queries log. So I’ll gladly drop the wordpress way and build the query manually. The first thing is that I can eliminate the need for the wp_term_taxonomy table (I can use the term_taxonomy_id instead of term_id, I never understood why wordpress needs both) but I still have the NOT IT ( SUBQUERY ) problem due to the categories to be excluded.

So considering that I’m free to do anything (like create other “service” tables if they might help), what’s the best way to speed up this search under these conditions?