message has been deleted

I have a similar problem before but for custom segments. Check the record type itself if the Include In Global Search box is checked and/or the Permissions tab (for custom segments, this prevails over the Custom Segment permission in the Role record).