iMessage not working between 2 people, others ok

Are the Apple IDs used and phone numbers appear correctly under Settings > Messages ? Maybe wrong phone numbers or email addresses are messing that.

Use Messages with your iPhone, iPad, or iPod touch - Apple Support

Does FaceTime between those two devices work?

Not true. If network (either wifi or mobile data) is an issue between the device and the server, Messages "falls back" to SMS. OP said there is indeed a delay in their SMSs also, so that could be -could not be- the cause.

If both devices are iPhones and iMessage is turned on and SMS switched off, if there are network issues, the messages won't be sent.

https://www.apple.com/support/systemstatus/

Try this in addition to what you have done

1. Delete any existing conversations on both sides

2. Delete each other's contacts on both phones

3. Log out of iMessage

4. Sign out of Find iPhone

5. Sign out of iCloud

Force restart both phones

Sign back in to all of the above

The only other suggestion I have is to try and use Apple's iMessage Deregister service to force a reset of iMessage in relation to the Phone number. This service is designed to deregister devices for people who forgot to log out of iCloud when they sell or give away their old iPhones.

Before using this online service turn off messages on the iPhone.

https://selfsolve.apple.com/deregister-imessage

Normally, when you turn off Messages in the iCloud settings on the device, it should deregister the phone number from Apple's iMessage servers. Then when you enable it again it reregisters the phone number. If there was a partial failure with the registration it might cause problems.

On top of my head as I review settings in my device:

Settings > Messages > Send as SMS turned off?

The iMessage gods took pity on you and decided to bestow you with the gift of a working Messages app.

Maybe yes, there have been some issues these days with some services as you can see in Apple - Support - System Status

People have had issues with their Apple IDs and App Store and iTunes purchases, not all, not every service, though.

Make sure that these people haven't accidentally added each other to the "Blocked List"

Go to Settings > Messages > Blocked and check the list of blocked numbers or IDs.

That shouldn't make a difference in this case since both devices are iOS therefore they would use the iMessage protocol not SMS.

I understand what you are saying but the OP is trying to solve an iMessage protocol problem. The OP stated that they do receive SMS messages, delayed but they still receive them.