Quain & Quaid are pretty much interchangeble surnames in Ireland, so they still could very well be related if you go back far enough. But it is an extremely difficult task.
It took me forever to get anywhere on my Quaid's until one day I called Ireland and spoke to a random Quaid in the area. He told me to call another lady & she is turn hooked me up with another fellow-was a Quain & happened to know ever Quaid & Quain in Ireland & the countries backward & forwards.
Recently I found a searchable online website to search Irsh church records- you can view for free but have to pay 5 pounds to view the record. I found quite a few of my family on this website.