Thanks for all your suggestions -- exactly what I'd already done!
It sounds like Houston accepted a church record only. As far as I understand, NYC requires a civil birth record -- can anyone confirm this? I didn't have either at my first appointment. I did subsequently find his baptism record, which took some doing.
My GF's marriage record had no indication of where he'd been baptized (and I pestered those poor people repeatedly). I'd already exhausted the closest churches (2-3 queries, donations to 2 churches) and had moved on to all the churches within about 1/2 mile of where they lived in Little Italy.
To make a very long story shorter, I returned to the archives and went through my GF's brother and sister's marriages. By the 3rd one of those, I found a baptism record for his sister (her actual baptism record in Italian from Most Precious Blood Church on Mulberry Street), which had been photocopied along with her NYC marriage record. Of course it was from the very first church I had queried, had the woman on the phone while she was actually searching the book, etc. Over two years had passed. By this time we had good reasons to question my GF's year of birth, which made things much more complicated.
I decided that I needed to go in. Turns out the previous secretary had retired just a month earlier! The new woman couldn't have been nicer, and within about 5 minutes we had the baptism record -- exactly where it should have been in the first place. The listing was under "Crestino" rather than "Cristino." Despite having a correct birth date, the original person passed it by each time. So I will reiterate what I've said before, which is to Just Keep Looking!
The other information that I dicsovered that may be helpful to others is that NYC also has a street index to their birth records at the Municipal Archives. So if you have the address where your ancestor was born and a good idea of the year, you can search there. That helped me find the 1900 Census -- on a page I'd already found over a year before. The names were so mangled that despite having saved it on my computer, I didn't even recognize them when I first saw it.
I was very lucky that my family stayed put. And the fact that families often had a lot of children in those days really helped me in the end as well.



