That's not true for me on iOS. I denied it access to my contacts, and I can still start a new conversation by entering a recipient's phone number.