K-9 Mail is sending messages using your outgoing mail server. As soon as the mail server accepts the message, K-9 Mail will upload the message to the Sent folder. It’s then up to the mail server to make sure the message is delivered. If there’s a temporary error, the server usually retries for a couple of days before giving up and sending you an email about the failed delivery.
It’s possible that K-9 Mail 5.800 is creating messages that are slightly different than those created by 5.600. And it’s also possible that some mail servers don’t like something about the “new” messages. However, without a detailed error report from a server rejecting such a message, there’s not much we can do.