Prestação de Serviços para Empresa Estrangeira - fatura-recibo?

Boa tarde!

Comecei agora a prestar serviços para uma empresa alemã. Tenho actividade aberta (CIRS 1332 - Programadores Informáticos), e agora pretendia emitr uma fatura para o cliente.

Emitindo uma fatura-recibo, tenho só um problema: a empresa diz que precisa do prefixo "PT" antes do meu NIF.

Será que têm razão?
Se sim, isso será possível de resolver usando algum software de facturação, que me permita colocar o prefixo "PT" (sem que fique depois inválido cá em Portugal)
Para o tipo de actividade que abri, posso apresentar as faturas à AT através do software (ou enviando o SAF-T) pelo site do e-fatura?

Estava à espera que isto fosse bem mais simples, mas já estou a desesperar...

Obrigado desde já!

Não, o nosso NIF são só 9 algarismos, sem letras, e é assim que tem que ir, e é esta a resposta que tem que ser dada ao cliente.