How to improve performance of a query matching on the same table
You can split your query into two different queries allowing for two different covering indexes to help you find the rows faster.

One query that checks FirstName and another that checks BirthDate.

select C1.CustomerId,
       C2.CustomerId
from dbo.Customer as C1
  inner join dbo.Customer as C2
    on C1.CustomerId &lt;&gt; C2.CustomerId and
       C1.FirstName = C2.FirstName and
            (
              C1.EmailAddress = C2.EmailAddress or 
              C1.MobilePhoneNumber = C2.MobilePhoneNumber or 
              (
                 C1.HomeAddressLine1 = C2.HomeAddressLine1 and
                (C1.HomePostCode = C2.HomePostCode or C1.HomeSuburb = C2.HomeSuburb)
              )
            );


select C1.CustomerId,
       C2.CustomerId
from dbo.Customer as C1
  inner join dbo.Customer as C2
    on C1.CustomerId &lt;&gt; C2.CustomerId and
       C1.BirthDate = C2.BirthDate and
            (
              C1.EmailAddress = C2.EmailAddress or 
              C1.MobilePhoneNumber = C2.MobilePhoneNumber or 
              (
                 C1.HomeAddressLine1 = C2.HomeAddressLine1 and
                (C1.HomePostCode = C2.HomePostCode or C1.HomeSuburb = C2.HomeSuburb)
              )
            );


The index you need to support those queries:

create nonclustered index IX_FirstName on dbo.Customer(FirstName) 
  include(EmailAddress, MobilePhoneNumber, HomeAddressLine1, HomePostCode, HomeSuburb);

create nonclustered index IX_BirthDate on dbo.Customer(BirthDate) 
  include(EmailAddress, MobilePhoneNumber, HomeAddressLine1, HomePostCode, HomeSuburb);


In my rather limited test case I saw an improvement from more time than I care to wait down to 4 seconds*.

The query plans I got for the two queries.






*I actually started the original query and forgot about it. Scratched my head trying to figure out why my computer was sluggish and found that the query had been running for 40 minutes.