In my opinion, your Portuguese customer is mistakenly confusing domestic tax laws with imports.
Here in Spain, there is a similar concept. We need to withhold part of the payment to freelancers, and pay it to the government. The freelancer claims that withheld amount towards their income tax liability. I believe this is firmly in the "why use a simple solution when a difficult solution suffices".
However this is ONLY for Spanish companies/freelancers paying Spanish freelancers. I'm quite certain that in the Spanish case, as well as in your Portuguese case, the requirement for withholding a portion of the payment is completely irrelevant to you as a UK business. I believe your customer doesn't realise that this law only affects domestic invoicing.
If you want to be certain, find a forum for ex-pats living in Portugal. Accountants specialising in ex-pat affairs frequent those forums, and one will certainly be able to clarify your situation. I realise you are not asking as an ex-pat, but I recommend this solution from experience. This forum looks adequate: http://www.expatsportugal.com/forum/viewforum.php?f=2&sid=f37feea585fe6321edfa069a347cac4f