IOS 13.3.1 iPhone 6s
I tried the previous examples and none worked. I went to the Settings/Phone and turned off Wi-Fi Calling and Calls on Other Devices. Then went into and deleted the the unwanted messages. It also let me go in and permanently delete them when it previously wouldn't. I turned both back on and all is good!