lookout: Update. It’s working for me now. I had to reset network settings and turn iMessage on again.
This is a pretty normal procedure and I think that telco's should always recommend that new customers do this to ensure best performance on network.
Edit: I just noticed the OP hadn't changed network so my comment not directly apply. But as part of troubleshooting, resetting network settings on iPhone is often useful, along with switching iMessage OFF and then ON.
I've done both of these sadly without resolving the problem.