If you'd had a private address in Germany, Canada, or wherever when you were based there, would you not have paid tax in that country? I'm guessing you would have.
I moved a round the world quite a bit whilst I worked for Raytheon.
The standard arrangement was that when I lived abroad the deducted the same amount from my UK salary as they would have for tax and NI whilst I was in the UK and paid my NI stamp fee. They provided details of one of their accountants in my country of residence who liaised with me and submitted my tax return. The bill was then paid by Raytheon. Once I had a local bank account set up I could nominate a set monthly amount and they would pay it into my bank account at a fixed rate and pick up the transfer costs (yes, if the rate was in my favour I could transfer back or forth on my own).