You don't have to go to specialist stores; you can get vegetarian Parmesan in at least twothree of the major UK supermarkets!
It seems to usually be under each supermarket's "budget" branding. I believe the reason for this is that "Parmesan" is a "DOP" name which means that it has a designated origin and legally has to be made in a particular region and with a particular recipe, which includes animal rennet. Since they're not calling it "Parmesan" but rather "hard cheese", they can do away with the animal rennet and also make it domestically which is cheaper, hence the budget branding:
Sainsbury's
Source: this site or many other places online.
Tesco's
Source: my Tesco's shopping trolley, today.
I haven't checked Asda's or Morrisons, but the two above are probably the biggest two of the Big Four supermarket chains; there must be very few towns in Britain that don't have *either* a Tesco's *or* a Sainsbury's.
Morrisons
Morrisons also have vegetarian hard cheese under their "M Savers" brand, which is clearly marked with their green leaf vegetarian motif. This is available in both grated form and in a solid wedge.
Source: Morrisons' own website.
Since those three large supermarkets offer vegetarian hard cheese, it's reasonably likely that others e.g. ASDA may offer a version.