Solution
I had this problem for about a year and could not find a fix for it. Finally after running into another problem, I restored my phone and set it up as a new phone. Immediately after I could send iMessages over the cellular data network. The key is to
Set up as a new iPhone
Do not restore from a previous backup.
What causes this problem I still don't know. I do know this fixed it for me though. Hpe this helps.