Locating all records relevant for a specific date
No INDEX can handle that OR.  Nor can any combination of indexes.

UNION can help with the first 2 range tests, but it won't help with the 3rd.

The 3rd range may include one-fourth of the table.

Is there any limit on the time between Adding and Updating?  We might be able to use a partitioning or spatial trick with that information.

Barring that, I recommend a UNION DISTINCT of the 3 tests, together with these two indexes:

INDEX(AddedDateRecord, LastUpdateDateRecord)  -- for Q1 and sometimes Q3
INDEX(LastUpdateDateRecord, AddedDateRecord)  -- for Q2 and sometimes Q3


The UNION is needed because MySQL is not good with ORs.

The DISTINCT is important because you can get dups.  To be faster, change to ALL and worry about the case where both columns are exactly date:00:00:00 -- where all 3 tests succeed.

Don't trust what you find for LIMIT, unless there is a significant pattern to the order how the rows were inserted.  Also, we need to see the PRIMARY KEY.