The biggest problem is people who would consent, but just never bothered filling in the form.

I think asking people this question when they apply for a passport would be a good middle ground, and/or maybe on the intake form for their GP, or other kinds of government interactions (voting registration might make sense in the UK specifically). People would still be able to opt-out of choosing at all, but this would catch the large group of people who just never bothered to register.