To follow up on this, I did go the Verizon store where I originally purchased my iPhone 5, and they replaced my SIM card with a new one free of charge. With the new SIM, my phone has been working flawlessly once again.
The problem is apparently a corrupted SIM card. This is something that happens occasionally and randomly. While iPhones running iOS 7 may appear to have a higher incidence of corrupted SIMs, this has happened with previous-generation iPhone as well as other brands of (non-Apple) phones, both GSM-only phones and GSM/CDMA capable phones like the iPhone 5 and up.
Bottom line: While the "no SIM" error is a PITA, there is an easy fix. Just get a new SIM card to replace your corrupted one. If you're on contract with a decent carrier, they will likely replace your SIM free of charge.