Truecaller does pull in your phone number and contact info into its databases so it can provide the blocking services it provides. A lot of those same alternatives have to do the same thing. Truecaller did get hacked into and their database data compromised, so that's a notable ding on their record. But there are very few, if any, online services that can claim they haven't had problems securing their servers.
A big problem in today's Internet is so many people are paranoid about their online privacy so they're very reactionary to any and all such revelations. They expect the same level of service and benefits, but without having to divulge any information about themselves to make those services actually work. Add in the corporate greed factor, (Facebook being a good example) and this only muddies the situation as a lot of people then mistakenly assume all data mining is bad, basically just making prejudiced accusations at any service accumulating data whether it's to provide a useful service or just to make profits.