iammoving.com was recommended to me by the estate agent who advertised the house we’re moving to in August.
After registering, for free (though I would pay for the service), you select the organisations you need to notify from a large, categorised list, and provide your account number (or whatever detail is appropriate).
You can then send each message individually, or send them all at once.
Unfortunately, some companies still require that age-old ink on paper malarkey. In these cases, a preformatted letter is made available to print.
iammoving.com is ‘in association with Royal Mail’, which makes sense because it could save them from thousands of undeliverable/redirected letters.