I had this issue with my last address, so when I moved to my current house and started seeing mail for the previous owner as well as what I assume to be the owner before him, I immediately wrote 'No longer at this address, return to sender" on all mail that wasn't for me - even spam mail - and made a support ticket on the USPS website. I felt like it was a bit overkill, but I did stop seeing mail for other people pretty quickly.
Dunno how quick Royal Mail would be comparatively, but maybe they'd be just as effective as USPS was for me.