I research the Irish Family History Foundation's database. It contains 12,000,000 surviving rcds for abt 65% of Irish counties. Rcds are increasingly sparse B4 1840, rare B4 1800.
Note 1 - Without a KNOWN county, the chance of an ancestor's rcds NOT being in this database is AT LEAST 35%.
Note 2 - Only 1/2 of Co. Cork's rcds are in this database.
Note 3 - The RC church kept control over most parish rcds from Tipperary (north). These are ONLY available thru the Tipperary Family History Research center at a substantial fee (regardless of outcome).
For Thomas Fahey B 1828 (exact) somewhere in Ireland with the father's forename unknown, I found 6 rcds: 1-Down, and 5-Galway.
For Mary Gannon B 1823 +/- 4 yrs ditto, I found 35 rcds.
You didn't state whether they married in Ireland or America. If Ireland, it is easier and more conclusive to search for a marriage than for B rcds.
Google the Foundation's name to lead you to this database. Register, opt to be notified as rcds are added and browse. Pls post your search results to my genforum msg.