Based on symptoms and troubleshooting so far, I have no iPhone specific thoughts/recommendations other than to try Settings --> General --> Reset --> Reset Network Settings. Unfortunately that will necessitate re-establishing WiFi connections.
On any type of phone, I'd be checking to see if calls made from the phone work consistently, and then try making some test calls to the phone after it's been idle for a while. I've found that sometimes the first call will go to VM, while a subsequent call to the phone right afterwards will go through (or, calls can be received after a successful outgoing call is terminated)... if this is the observation, I often focus on antenna/signal issues. As others have mentioned, having another phone to test on is useful to confirm it is indeed isolated to the phone, but based on symptoms, it usually is.
