Instead of creating a transaction container and then sending it to the receiver COD, you could simply create a "pay another transaction's fee" transaction type. There's no need to cryptographically guarantee that the postage is only paid by the recipient, so let anyone throw in some extra tx fee.
Like I said, that would be the long term goal. However, that requires the same work we have to go through for P2SH, and you know how well that's turning out. The short-term solution I detailed could be added to all of the miners today, if the code existed.