Как правильно написать css селектор с регуляркой?
Селектор :not работает только с простыми селекторами: элементов/тегов, классов, псевдоэлементов, универсальных(*) и идентификаторов.
Можно вот так:a {
   background-color: #999;
};
a[class^="bg"] {
  background-color: something;
}
В качестве дополнения предыдущего ответа
https://www.w3.org/TR/css3-selectors/#negation 
The negation pseudo-class, :not(X), is a functional notation taking a simple selector (excluding the negation pseudo-class itself) as an argument