Użytkownicy SQL wyszukujący zapytanie

Myślę, że to powinno wystarczyć:

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%')
      )

Musisz przetestować każde kryterium osobno, a nie każde pole.