Search for contacts within Geocoded regions/borders
We had a similar need and used mapit: https://mapit.mysociety.org/. Every time an address is created/updated we use the mapit API to grab the associated parliamentary constituency, European region etc. It looks like the mapit API can give you England/Wales/Scotland/NI too (though it's trivial to translate from the European Region).

We did similar to @ErichBSchulz and created a custom field that is populated by this API lookup. We then have smart groups running off that.

Happy to share our somewhat hacky extension if it'd help, though you'd need to adapt it to your needs. Caveats are: it only works if you have the full postcode; currently we don't have a way to run it for imports; you'll need to populate your existing database somehow (we have a million-row excel spreadsheet we got from one of the government's open data things).

At one point Veda Consulting were working on a service that did something similar - possibly building on top of their postcode lookup service. Might be worth pinging them in case they have something more robust.

EDIT: published this extension at https://github.com/bhahumanists/bha.politicaldata