Apr 052012
After I received the marriage certificate from the church, I sent back the "no record found" to the City of Buffalo (along with a copy of the church's certificate).
Today they sent me the certificate. I guess now they actually searched a bit harder.