I believe, Truecaller is an auto opt-in and you have to manually opt out if you want your number not be listed. I had to "unlist" my number manually. Check if your number is already in and then unlist at https://www.truecaller.com/unlisting
Seems seriously shady.
How do you check whether your number is "in"?
Once you do, you have to log in with either your Google or Microsoft identity and agree to let them download your contacts.
Since they have already done an action without your consent or agreements they should be able to remove you permanently without requiring you to agree to anything, signing up or mailing crap.