Is there a quick way to find out what posts haven’t been tagged?

I think this could get resource-intensive quickly, but fastest API way would be to create list of tags and query for posts that do not belong to any:

$tags = get_tags();
$ids = array();

foreach ( $tags as $tag )
    $ids[] = $tag->term_id;

$posts = get_posts( array( 'tag__not_in' => $ids ) );

If you have large amount of tags or need to do this often it is probably better to look into building raw SQL query for this.