Incorrect query results for execution plan, unsure of exact cause of problem
I don't believe that result was incorrect at all, your query is ambiguous. Semantically your subquery enumerates all rows and then you pick the top 25 rows without specifying an order by. That means that SQL server is at liberty to return any rows it feels like and those rows do not have to be the rows enumerated 1 to 25. It can be just any random rows and in your case four of the rows was enumerated in the range 1 to 25. The rest was filtered out in the main query. 

You can fix the query by removing the top statement in the subquery.


  In your opinion based on the query what would be the best course of
  action?


I would test all the options you have and pick the one that performs the best. 

I will give you one more option to test that assumes ID is the primary key column in TableC and that AddedDate is not the clustered key.

Add an index on AddedDate including the columns you need to filter out rows before the enumeration happens.

create index IX_TableC_AddedDate on TableC(AddedDate) 
  include(AccountID, Processed, Deleted, Source)


Rewrite your sub query so that the only returns ID and row and then join back to TableC in the main query to fetch the rest of the columns.

SELECT E.Row,
       C.*, -- don't use * here, include the columns you actually need
       (
       SELECT COUNT(*) 
       FROM TableA as A
         LEFT OUTER JOIN TableB AS B 
            ON A.GRRecID = B.GRRecID
       WHERE A.AccountID = @P1 AND 
             A.Email = C.Email AND 
             A.Deleted = @P2 
       ) AS Matches
FROM (
     SELECT ROW_NUMBER() OVER (ORDER BY C.AddedDate DESC) AS Row,
            C.ID
     FROM TableC as C
     WHERE AccountID = @P3 AND 
           Processed = @P4 AND 
           Deleted = 0 AND 
           Source = @P5  
     ) AS E
  INNER JOIN TableC as C -- Join back to TableC
    ON E.ID = C.ID
WHERE E.Row &gt;= 1 AND E.Row &lt;= 25
ORDER BY E.Row


There might be an even more efficient index you can try but the datatypes for your parameters are somewhat confusing. Is AccountID really a varchar(8000)? If not you should change the data type to match that of the column and in that case a better index to use would be to lead of with AccountID. 

create index IX_TableC_AccountID_AddedDate on TableC(AccountID, AddedDate) 
  include(Processed, Deleted, Source)


The same goes for Source depending on what datatype it is. If the datatype appropriate you could add that one as well before AddedDate in the columns list of the index.

You could even use all the columns from the where clause in the index if like to avoid any residual predicate.

create index IX_TableC_ on TableC(AccountID, Source, Processed, Deleted, AddedDate)


Just make sure AddedDate is the last column in the index and that you don't have any columns before AddedDate that is not used in the where clause.

A blog post by Itzik Ben-Gan on the same lookup problem (for offset-fetch):

Avoid Unnecessary Lookups when Using ROW_NUMBER for Paging