REGEXP är ganska resurskrävande och gör att index inte kan användas (vilket kanske även gäller LEFT() beroende på hur klokt MySQL är).
Kod:
WHERE domain LIKE 'x%' AND domain NOT LIKE 'xn--%'
Borde väl fungera? (Och då kan index användas om du har indexerat domain)