Penso che questo dovrebbe farlo:
SELECT * FROM `users` WHERE (
(firstname LIKE '%mat%' OR lastname LIKE '%mat%' OR
phone LIKE '%mat%' OR email LIKE '%mat%' OR username LIKE '%mat%')
AND
(firstname LIKE '%h%' OR lastname LIKE '%h%' OR
phone LIKE '%h%' OR email LIKE '%h%' OR username LIKE '%h%')
AND
(firstname LIKE '%50%' OR lastname LIKE '%50%' OR
phone LIKE '%50%' OR email LIKE '%50%' OR username LIKE '%50%')
AND
(firstname LIKE '%@l%' OR lastname LIKE '%@l%' OR
phone LIKE '%@l%' OR email LIKE '%@l%' OR username LIKE '%@l%')
AND
(firstname LIKE '%d%' OR lastname LIKE '%d%' OR
phone LIKE '%d%' OR email LIKE '%d%' OR username LIKE '%d%')
)
Devi testare ogni criterio separatamente, non ogni campo.
