The Registry of Births Deaths and Marriages in Gibraltar is a good place to contact for certificates of birth. As long as you have some detail they are very helpful and I have had several certificates from them.

I also have had contact with the Cathedral of the Holy Trinity and received certificates of baptism or marriage from them.

Jackie