Boa pergunta Clayton!
Sim, o not nega a expressão inteira. Então é como se fosse not (all and (max-width:600px) ).
Esse all é um media type. Outros valores famosos possíveis são screen e print por exemplo.
Antigamente no CSS2 a gente só tinha media types, aí no CSS3 inventaram as media queries (como o max-width). Só que a especificação atrela as duas coisas; isso quer dizer que todo @media obrigatoriamente tem um media type mesmo se você quer apenas usar um media query.
Então quando você escreve @media (max-width:600px) apenas, saiba que existe sim um media type escondido, que é o all. Logo seria a mesma coisa que escrever @media all and (max-width:600px).
O problema é quando vamos usar o not. A especificação não deixa usarmos o not direto na media query. Ele nega o bloco @media inteiro então acharam uma boa ideia o media type ser obrigatório e estar visível.
Por isso é inválido escrever apenas @media not (max-width: 600px) e precisamos colocar o all aí na jogada e escrever completinho: @media not all and (max-width: 600px).