(Some of this may be well known to you but I include it for completeness and to help others facing similar problems).
The first places (in England and Wales) to search for a birth registration are:
The GRO indices (which have come on line recently-- registration required but they're free to use). In theory, this should be the best place to start as they have been recently produced from the certificates (and so avoid some of the problems of the original indexes) but the search facilities are not great -- in particular, you must specify a surname (wildcards are not allowed) and a gender; and you can only search across five years at a time. When you have an unusual (for the UK) and so often mis-spelled or mis-transcribed surname such as Gazzanovich, it can be hard to construct an effective search.
FreeBMD, which is a searchable database based on the original GRO indices, and allows more flexible searching.
My usual approach is to start with FreeBMD and then confirm the results in the GRO indices (which include mothers maiden name for all entries).
Whichever you choose, you need to determine your search parameters.
Surname
Such an unusual surname is almost certain to be mis-transcribed/mis-indexed so try wildcards .. e.g G**z* or even G* or C*.
First names
Santa Catherine ought to be unusual enough to show up, but consider that she might have not have been named at the point her birth was registered, or registered as Catherine (but later baptised as Santa Catherine).
Time period
Ages in the census are notoriously unreliable. If Mary Evans married Nicoli Gazzanovich in 1875, then 1880 was quite late for a first child to be born. However, she was definitely not with her parents in the 1881 census, so perhaps she was born later in 1881?
The latest point at which she could have been born is 6th May 1887 when she was baptised in Roath -- the record is on FindmyPast with images, but also on FamilySearch.org.
Do you know her age at marriage in 1900 (from her marriage certificate?) If she was of full age at marriage (which is statistically most likely) she would have been born before 1879. If she was a minor, she might have been born as late as 1884.
Place
Given where Mary Evans was born and where she lived with her husband, a birth place of Glamorgan or Breconshire is most likely (Merthyr Tydfil straddled the two counties).
Neither FreeBMD not the GRO indices return any results in those two counties between 1875 and 1887 which look at all likely to be a match. (Nor do they throw up any possible siblings, or any strong possibilities elsewhere in England and Wales).
One possibility is that her birth (and the births of any siblings) were not registered -- however this is highly unlikely at this late date.
The second possibility is that her birth was registered under another name -- i.e. that she was adopted, as you have suggested. If she was born around 1880, this might account for the (very late) baptism in 1887 and for her absence from the family household in the 1881 census. A total lack of siblings also suggests that Mary and Nicoli had problems having their own children...
Adoptions at the time were informal, so there will be no records of it. You could try looking for the birth of a child named Catherine on 19 June 1880 (assuming she had remembered her date of birth correctly, and that her name was not changed by her new parents except to add a baptismal 'Santa').
The online indices will not help with this, but the Local Registrar in Merthyr Tydfil should be willing to search for a Catherine born on that exact date... I used the same technique to find the birth of my great-grandfather -- I had a date and place of birth and a very common name (Tom Jones) but no parents names, and the Merthry Tydfil registrar located the certificate. In another example, my great-grandmother was always definite about her birthdate and place but we could find no birth registration for her with the parents we knew about. Again, the local Registrar (Caernarvon this time) tracked down the only birth certificate for a Margaret Jones on the correct date and we learned that she was born illegitimate and later adopted by the parents we knew about.