This isn't really a solution as much as an answer. My girlfriend has a Series 4 LTE+GPS model on Verizon and a friend of mine has a Series 3 LTE+GPS model on Sprint. I saw them over the last few days and they were kind enough to let me test things.
Both Apple Watches behaved in the same way. Sending / receiving SMS while using a cellular connection was difficult and out of 10 tests per device, including mine, we only got them to send an SMS and receive a reply 4 times out of 30 tests. Since 3 carriers and 3 different models had these same issues, I am personally concluding that it is some kind of software issue. Since the devices are primarily designed to work with a cell phone within range, I expect that there is some as-yet-unknown issue in this specific though possibly rare use case.
We cannot packet sniff or do other advanced diagnostics on how the watch communicates with the cellular network to accomplish its tasks. This fact combined with the fact that most tech support agents you can speak with on the phone at a carrier are simply running off of checklists without being knowledgeable in how their network actually works leads me to believe that this problem will have to wait for a carrier solution.
I believe the issue is with how it appears the watch sends and receives SMS while away from the phone. The iPhone is required to be turned on and connected (I quote the article linked in my question):
Make sure that your Apple Watch can connect to your iPhone, cellular, or Wi-Fi. To send and receive SMS/MMS from cellular models of Apple Watch, your paired iPhone must be powered on and connected to Wi-Fi or cellular, but your iPhone doesn’t need to be nearby.
Even if your iPhone isn’t connected or powered on, you can send and receive iMessages on your Apple Watch when your Apple Watch is connected to Wi-Fi or cellular.
This indicates to me that the watch uses UMTS for phone calls but not for SMS. Since phone calls with the watch under cellular can be completed without the assistance of the paired phone. I tested this just to be sure and powered off my phone but could still make and receive calls on the watch perfectly. It appears the watch intends to send it's SMS messages to its paired phone over iMessage to then be relayed through the phone's cellular connection. Similarly the phone appears to receive an SMS first and then relay to the watch similarly. I did delay testing using the watch connected to WiFi only and the phone only connected to cellular. The phone would receive the SMS first and between 0.5 and 2 seconds later the watch and other iMessage devices would receive the message as well. Likewise testing sending under the same conditions the watch would send a message, it would then hit the other iMessage devices in roughly about a second, then 3-4 seconds after showing up on iMessage devices connected to my iCloud account it would show up at the receiver.
If I turn off the phone sending and receiving SMS fails to work (as the Apple documents indicate) on any iMessage device (this includes my iPad which has its own cellular connection and my two MacBooks).
Given all of this, I am convinced that there is a relay problem due to network provisioning and connectivity issues for the SMS relay to take place while the watch is using cellular data.
This is backed up by an experience I had previously in testing the ability for a cellular device to run an internet service. I had attempted to run a small web server on an Android device on my AT&T account and was unable to open a port on the Internet side of the connection. The test was part of a University project and not part of this testing. Technical support from AT&T indicated that they specifically make it difficult for devices on their cellular network to be directly accessed on the Internet unless the device has been specially provisioned. It was also indicated that this was done in the name of security but in the same call such provisioning was possible under specific request for a business account holder and would cost extra to implement.
Given these factors I'm considering the issue closed. I believe the watch uses iCloud to relay information to/from the phone for SMS (and possibly other) functionality and that cellular services make it extremely difficult to establish this kind of connection reliably for standard cellular clients.
