Veamos, puedes usar esto:
SQL: UNION
Seria algo así:
Código PHP:
$buscauser=mysql_query("
SELECT `key` FROM `CurrentUsersPlaying` WHERE `key`= '$lastname'
UNION
SELECT `key` FROM `CurrentUsersPlaying2` WHERE `key` = '$lastname'
");
Así combinas el resultado de las dos consultas en 1.
¿Optimo? No lo se. Tb podrías, simplemente, primero consultar una tabla, y si existe, está online. Sino, consultar la otra, si existe, está online, sino, offline