This might sound a bit crazy, but... the UK government is in sole control of .gov.uk, right? They shouldn't have issues issuing themselves with as many subdomains as needed. For free, or for symbolic prices.
.gov.uk domains are registered through commercial registrars (who charge a fee), much like .co.uk domain names. The main difference being that you need to be an eligible organisation to register a .gov.uk domain name.