I would agree that a many to many is not a the way I would choose here. There is nothing to be gained by this. Yes it is possible that you can have multiple contacts with the same phone number. For this type of thing a small amount of data redundancy is not a big deal.

I understand what you are saying that you want to allow for as many phone numbers for a given person as they want. What I don't understand is how that creates orphans. I would establish that a foreign key with cascading delete. That way if you delete the contact, all of their phone numbers get deleted too.