Why does a deleted contact's name continue to show up in Messages? I deleted a contact from my iPhone. However when I type that person's name when sending a text message, their contact details still show up as their name and other: 111-111-1111. 

I did a reset keyboard dictionary but no luck. How can I fix this?
Unfortunately, this issue is rooted within iOS itself. Your phone automatically caches contacts for messages so that they can quickly be accessed when you're typing in a name or number, rather than querying the contacts app every time. 

The only solution I have found to this is a full factory reset.

The reason being that data from the Messages app can only be changed by the phone itself, because of the nature of iOS, therefore the only way to force the phone to overwrite the caching in the messages app is to force the phone to overwrite the data in all of its apps.