A maneira mais eficiente seria comparar seu timestamp (e apenas timestamp, sem usar nenhuma função nele) com uma expressão que pode ser calculada como constante para cada linha, desta forma o mysql pode usar o índice definido em sua coluna timestamp.
SELECT * FROM myTable
WHERE last_seen >= NOW() - INTERVAL 10 MINUTE
Você sempre pode tentar
EXPLAIN SELECT ... para ver se um índice pode ser usado para encontrar linhas que satisfaçam sua condição WHERE sem a necessidade de verificar cada linha na tabela. 
