getting rid of duplicates too:

select username
from table
where username != ''
and username not like 'deleted%'
and username not in (select username from other_table)
group by username
having count(*) > 1;
[download]

I've never used mysql, but in other RDBMS systems I would check that enough memory has been assigned to buffer cache, sort area, hash sort area, etc. And by "enough", I mean "lots".

Joining two 34M rows on a decent enough server shouldn't take long. Nested iterations over 2 large tables does take a long time.

Having indexes on username on both tables would help a lot too