My daughter who now lives in Australia has lost her British Birth Certificate and now needs to obtain a replacement. This is where the difficulty lies, she was born in Gibraltar, when we resided there via the British Forces, her birth was registered in Gib (and she still has a copy of her Gibraltarian Birth Certificate) and also in the UK. Her birth registration in the UK, was carried out via the armed services, so I do not actually know where the birth was registered. I guess perhaps St Catherine's HOuse in London. I have tried to track her birth certificate down via the web, but have been unable to find it listed.
Not an answer, but have you tried www.gro.gov.uk ?
If you cannot find what you want there, you can try asking to see if they can give any advice; the other possibility is that the armed service through whom the birth was registered in the UK may be able to at least tell you where it would have been registered.