Contacts missing when trying to send iMessage
Also would help to know if this specific device is the same one that's been in use for "years", and whether you've been icloud synching your contacts or not.

I think there’s a simple solution - create an actual Contact for them.