I'm having the same issue, it's frustrating!.
In the Contacts app, open one of the troublesome contacts and select edit.
Please confirm the phone number is entered in one string, preferably in its complete, international format and without white-space, brackets or dashes.
For example +0112345678
Local phone numbers can be entered as 12345678 but I suggest add the + country code for all, to make it work when outside your home country too.
Apps may add white-space etc. according to local conventions, in order to make the phone number more human-readable when displaying it on the screen, but the mobile networks require proper formatting.
Does this help?