iMessage Message not found
A posting on the Apple Support Communities suggests: 

https://discussions.apple.com/thread/4356067?start=15&amp;tstart=0


  "You must contact your cellular service provider. This is not an Apple issue, that causes this. The reason, that the phone just started doing this: when you power cycle your phone, it clears the system cache files. Your network has text alerts, from your basic Voicemail, where someone used a service, called "Cut-Through Paging". CTP allows a person to leave a text message, with their callback number, instead of a voicemail. Visual Voicemail smartphones can not utilize the feature. Your provider may have to delete your old voicemail box, and then re-add a new basic Voicemail feature, to correct the problem. You will have to pwr cycle the phone, after the chane and setup a new VM box. CTP was designed to be used, with basic and messaging phones, that do not utilize Visual Voicemail."


But please note, this is from 2014.

Two questions to ask yourself would be:

Does this happen when you restart the phone?

Does this happen when using or accessing voicemail?


Assemble as many details as you can about the event, including what may have triggered it. The same link above also has a comment indicating this happens on Windows Phones, too. It may be a carrier issue. I would recommend recontacting your carrier and ask them if the above scenario is plausible.