It took over 6 months to get my Certificate of Residency from the HMRC - which, as pointed-out earlier, looks only marginally more official official than something one of my 6th graders could have cobbled together...
The deal is that, yes, you need to pay tax in one of either Korea or Britain. Getting the tax residency certificate means you're not ordinarily resident in the UK, and so not liable to UK tax, only Korean tax. This is much lower than in the UK, so worth ensuring you're eligible for. As a bonus, Brits (and some other citizens) employed within the state school system (ie with EPIK or GEPIK) enjoy a two year tax free period here if they can prove residency within Korea for tax purposes. So, all round, worth pursuing, despite the significant hassle.