I heard once that one should never be tovel kelim with a bracha, since it is always a safek that a Jew made it since many companies have stocks owned by Jews. Is this true?

Only a utensil made by a non-Jew needs tevila, not a utensil made by a Jew or a Jewish-owned company. However, If something was made jointly by a Jew and non-Jew and subsequently purchased by a Jew, the utensil needs tevila. Therefore, even if a Jew owned stocks in the company, it would only be considered jointly owned between the Jew and non-Jew, and therefore it does need tevila.

Therefore, one should indeed make a bracha on any utensils purchased, unless there is a legitamite reason to assume the company is completely owned by only Jews (such as many companies based out of Israel).

See Shach (Y.D. 120:26). It is also not so simple that owning stocks is considered as having real ownership in a company, especially if the amount of stocks owned is not enough to have a real influence in the running of the company.