Rozdíl je v tom, že když použijete exists - dotaz uvnitř obvykle závisí na hlavním dotazu (tj. používá z něj sloupce a nelze jej tedy provést samostatně), a tak pro každý řádek hlavního dotazu zkontroluje, zda nějaká data získaná poddotazem existují či nikoli.
Problém vašeho prvního dotazu je, že poddotaz uvnitř existujícího bloku nijak nezávisí na hlavních sloupcích dotazu, je to samostatný dotaz, který vždy vrací řádek s 1 , takže pro jakýkoli řádek hlavního dotazu výsledek exists bude vždy true . Váš první dotaz je tedy ekvivalentní s
SELECT distinct(company_id)
FROM user
WHERE user.user_id = 123
AND user.company_id IS NOT NULL
Viz také fiddle