Den mest effektive måde ville være at sammenligne dit tidsstempel (og kun tidsstempel, uden at bruge nogen funktioner på det) med et udtryk, der kan beregnes som konstant for hver række, på denne måde kan mysql bruge indeks defineret på din tidsstempelkolonne.
SELECT * FROM myTable
WHERE last_seen >= NOW() - INTERVAL 10 MINUTE
Du kan altid prøve EXPLAIN SELECT ...
for at se, om et indeks kan bruges til at finde rækker, der opfylder din WHERE-betingelse uden at skulle tjekke hver række i tabellen.