Se você realmente quer apenas "6 caracteres aleatórios" e não se importa com o que está depois do :
, você pode simplificar facilmente. Não tente corresponder ao que está depois do :
, e use apenas .
para os caracteres após o PA
egrep '^PA.{6}@gmail.com:'
por exemplo,
% cat f
hello
[email protected]:jgkfd
[email protected]
[email protected]:
% egrep '^PA.{6}@gmail.com:' f
[email protected]:jgkfd