Pelo que eu sei, não tem como "selecionar" um elemento 'parent' ou 'child' através da propriedade `:not`, diferente de um seletor `:first-child`, por exemplo, ou `:nth-child(n)` que consegue fazer essa seleção.

O que pode ser feito, é aplicar uma classe de negação juntamente do elemento que vai possuir o span, assim você pode negar que seja aplicado o `css` àquele elemento, para isso usamos um `css` semelhante a esse:

html:

    <a class="button">Teste 1</a>
    <a class="button">Teste 2</a>
    <a class="button negado"><span>Teste 3</span></a>
    <a class="button">Teste 4</a>

css:

    a.button {
        background:#eee; //cor de fundo cinza
        padding:15px;
    }
    
    a.button:not(.negado) {
        background:#f0f; //tudo NÃO POSSUIR a classe .negado, terá o fundo rosa
    }

Veja o exemplo: http://jsfiddle.net/47x6g60z/

Outra solução seria de fazer o inverso, aplique o estilo somente àqueles que possuem o span como 'child', ficando assim: http://jsfiddle.net/47x6g60z/1/

<hr />

### Editado: Responder dúvida do comentário

Como não existe um modo de selecionar um parent ou child através do :not o modo mais fácil de conseguir o que você deseja, seria de definir a propriedade para todos os elementos e depois 'resetar' naqueles que você não deseja que tenha o estilo. Veja este exemplo: http://jsfiddle.net/47x6g60z/2/