I didn't know the answer so I looked it up. Nominatim gets postcodes from Ordnance Survey: https://nominatim.org/release-docs/3.4/data-sources/GB-Postc...
Specifically Code-Point Open: https://www.ordnancesurvey.co.uk/products/code-point-open which is updated quarterly, and in turn gets the postcodes from Royal Mail.