Well, it is obvious - make your ping value lower. Why you have it on 5 minutes? If you set it too low, you may have issues with clients randomly disconnecting. But you can find a value which works fine for your network, like 20-30 seconds. This won’t solve the issue, but will make it appear less.
The complete solution would be to use a client supporting XEP-0184: Message Delivery Receipts on both sides of the conversation. This way if message wasn’t delivered, the sender will receive a notification about that from his client. But that’s it, it won’t try to send it again on itself. I don’t know which clients support that already. Spark still doesn’t (SPARK-1238), though Smack (the underlying library of Spark) has it, so maybe at some day Spark will support this too.