Troubleshooting "Not Sent. Tap to try again." error in Android Messages

I use Android Messages to send SMS messages on my phone.  Sometimes I have a problem sending a message to a specific person.  I can still send messages to others, and I can still receive messages from everyone.  When this happens, it says "Not Sent. Tap to try again." underneath the message (see an example screenshot) about 20 seconds after attempting to send the message.  Once this problem starts, it does not go away on its own.  It will always happen when trying to send a message from within the app as well as from the reply feature on the notification of a new incoming message from the specific person.  It will not happen if I tell the Google Assistant to send them a message to the specific person and then dictate that message.

Here is a good sequence of troubleshooting steps for this problem (which can also be found elsewhere).

1. Restart phone
2. Clear app cache
3. Clear app data
4. Uninstall then reinstall app

I have tried all of these troubleshooting steps, and none of them deleted my conversations.  They are probably backed up somewhere.

This problem has happened to me twice.  The first time, I think I solved it by uninstalling and reinstalling the app.  The second time, I know that restarting my phone didn't fix the problem.  What did fix it was both clearing the cache and clearing the data.  I didn't try just clearing the cache.  If I am so mildly unfortunate as to experience this problem again, then I should check if just clearing the cache suffices.