That description is really helpful! Let’s see… The long delay is interesting—especially that the attempted message eventually appears on the other Mac, but never appears on the iPhone before ultimately failing.
That makes me wonder whether the two Macs are syncing the message between themselves through Messages in iCloud, while the actual outgoing relay through the iPhone is timing out.
Is Messages in iCloud enabled on all three devices?
On the iPhone, check Settings > [your name] > iCloud > Messages.
On each Mac, check Messages > Settings > iMessage > Enable Messages in iCloud. If it is already enabled, there should also be a Sync Now option—try that on both Macs and see whether anything changes.
Then I’d try one fresh test message from only one Mac, with the iPhone turned on, online, and nearby. I’m curious whether that message ever appears on the iPhone at all while the Mac is still showing the slow progress line.