Birth certificates
Ogre - My line of inquiry would be the British High Commission in Malta and Somerset House in London. Goggle them.
I was born in Kenya to civilian parents and have a certificate issued by the colonial administration of 'Kenya Colony'
My son was born at the RAF Wegberg while I was servivng in the then W Germany. The hospital staff very strongly advised us to get his birth registered at the British Consulate Dusseldorf before the host nation 'conferred' German nationality on him. At the time all German nationals had to do 2 years of National service. As we did not wish our son to guard some barracks in Schelswig-Holstein in the future, I scooted off to Dusseldorf and got him registered as a British national. No problems since.