This is a generic message and sources for this issue could come from multiple location. More than likely this is a IM&P server side problem. I would start looking at the IM&P server health from System > Cluster Topology if the servers shows in green checkbox state.
Second, I would suggest checking the replication of the IM&P Server (utils dbreplication status followed by utils dbreplication runtimestate on IM&P pub until the table count goes to full number.
On IM&P Server side for the logs, Presence Eingine, XCP Router and Syslog would be the one need to be analyzed (set a detailed level)
Also, if you are familiar with Jabber.log you can look for "SendInstantMessage" in the log and see what follows after it at the time when this IM delivery alert happpened.
If more help needed I would suggest a TAC case on this one.