Wordpress - Query all posts where a meta key does not exist

I did some more testing with this, and honestly can't find a reason it wouldn't work (unless the code above is just a snippet and the real code fits on my examples below). I did, however, discover a couple of things that might lead you in the right direction.

1) By itself, this meta query is the equivalent of "colors IS NULL", i.e. it'll return the posts which don't have that key set in the postmeta table. This is the case shown above, and it should've worked.

'meta_query' => array(
    array(
     'key' => 'colors',
     'compare' => 'NOT EXISTS' // this should work...
    ),
)

2) Prior to WordPress 3.9, establishing the 'relation' index to 'OR' changes this condition. It returns the opposite. Don't ask me why. This is especially important when doing multiple meta queries. That means that is not initially possible to do a query for posts that have 'colors' key set to 'blue' (or whatever) or not set at all. The query below will ignore the first condition and return only those that match the second condition.

'meta_query' => array(
   'relation' => 'OR',
    array(
     'key' => 'colors',
     'compare' => 'NOT EXISTS' // doesn't work
    ),
    array(
     'key' => 'colors',
     'value' => 'blue'
    )
)

3) However, we can fool WordPress into using the first condition if we set the 'value'. It doesn't need a relevant value (it's ignored, as far as I know), but it needs to be set in order for the NOT EXISTS condition to have any effect.

'meta_query' => array(
   'relation' => 'OR',
    array(
     'key' => 'colors',
     'compare' => 'NOT EXISTS', // works!
     'value' => '' // This is ignored, but is necessary...
    ),
    array(
     'key' => 'colors',
     'value' => 'blue'
    )
)

This was true up until WordPress 3.9. If you're still using an older version, this is a viable workaround.

Using a custom query, this worked for me:

SELECT * FROM wp_posts as posts
            WHERE   posts.post_type     = 'post'
            AND NOT EXISTS (
              SELECT * FROM `wp_postmeta`
               WHERE `wp_postmeta`.`meta_key` = "your_meta_key"
                AND `wp_postmeta`.`post_id`=posts.ID
            ) 

This worked for me.

'meta_query' => array(
   'relation' => 'OR',
    array(
     'key' => 'colors',
     'compare' => 'NOT EXISTS' // doesn't work
    ),
    array(
     'key' => 'colors',
     'value' => 'blue'
    )
)