Undeliverable Messages

I keep receiving a lot of undeliverable statuses on my messages (red triangle with exclamation mark on phone), however the messages seem to be sending.
Some messages also randomly show as undeliverable on Airdroid.

I'm having a similar error, in that every message I send from AirDroid is undeliverable and I have to click it on my phone and re-send it from there.

I am also having this error.