P* como regex significa "qualquer número de P s, incluindo 0". Por isso, sempre corresponderá, pois cada linha contém pelo menos 0 P s. Isso explica por que egrep -v P* imprime nada: cada linha corresponde e -v seleciona as linhas que não correspondem. (Na verdade, ele pode fazer outra coisa, pois P* será expandido por bash na lista de arquivos que começam com a letra P no diretório atual, se houver algum. Você deve usar aspas egrep -v "P*" , mas isso não é problema seu.)
Você deseja corresponder um P no início da linha. Então, você precisa especificar que o regex é "ancorado" (corresponde apenas no início), o que você faz colocando um ^ no começo:
grep -v ^P file.txt > new.txt
A propósito, egrep está obsoleto; você deve usar grep -E , mas neste caso não há diferença entre o regex básico e estendido.
grep não usa "globs", ele usa expressões regulares. E isso não força a expressão regular a corresponder à linha inteira; é suficiente se uma string correspondente à expressão regular aparecer em algum lugar na linha.