Optimized query to fetch a record from 10 million entries
The query to accomplish this would be of the form:

SELECT t.UniqueKey
  FROM mytable t
 WHERE t.UniqueKey = ?
   AND t.timeStamp &gt;= NOW() - INTERVAL 5 MINUTE
   AND t.timeStamp &lt;= NOW()
  LIMIT 1


(This query assumes that the timeStamp column is defined as datatype TIMESTAMP.)

The query will either return one or zero rows, which will indicate either that the specified UniqueKey does "exist" in the past 5 minutes, or that it "doesn't exist".

That query cries out for an index:

... ON mytable (UniqueKey,timeStamp)


If UniqueKey is truly UNIQUE within the table, then an index on just UniqueKey is satisfactory. Can't really determine what's best without knowledge for the column datatypes, storage engine, existing keys/indexes, data distribution, et al.



UPDATE

(the answer above was copied from StackOverflow, where the question first appeared.)

OP has updated question with sample data, illustrating that the timeStamp column is probably NOT a MySQL TIMESTAMP, but appears to be an integer value.

If we assume that it's stored as an integer datatype (e.g. INT, BIGINT, etc.), and that the integer value that is ascending in datetime order... then the most efficient query would be of the form:

SELECT t.UniqueKey
  FROM mytable t
 WHERE t.UniqueKey = ?
   AND t.timeStamp &gt;= ?
   AND t.timeStamp &lt;= ?
  LIMIT 1


The values are supplied in the predicates (to compare to timeStamp are assumed to be integer values. That's just an assumption, we don't have knowledge here that they actually ARE integer values, and we don't have knowledge of how the datetime is encoded.

It's very likely that timeStamp value represents the integer number of seconds since the beginning of the epoch (midnight Jan 1, 1970 UTC). That's a widely adopted convention, but it's still just a convention, not a "rule" that all columns with a name of timeStamp have values that are encoded this way.

So, I hesitate to make any further recommendations based on assumptions. MySQL does provide functions that make conversions possible, some very convenient. But without knowledge of what values are actually being stored in the timeStamp column. Those recommendations would be based on assumptions.