Pode deixar-se cópia certificada, já o fiz algumas vezes. E presumo que se se pagar por meio de guia não seja necessário deixar cópia nas finanças (quanto a isto não estou certa).
E mais: eles (finanças) não sindicam os contratos, claro... Só olham para a cláusula da renda, para calcular o IS.
Notificar pode ser através de carta registada com aviso de recepção enviada para o sitio onde ele trabalha (o imóvel arrendado). É notificar a conceder prazo para pagar. Depois é pegar nisso e no contrato de arrendamento e ir para executivo... Dura normalmente uns 5 meses. Mas notificar não me parece ser complicado (entenda-se: notificar não implica que a carta tenha que ser efectivamente recebida, se não levantarem a carta, é suficiente para provar a interpelação).