A technique is described herein for providing a personalized notification to a recipient-user. In one approach, the technique involves: receiving an original message sent by a sender-user; selecting a notification type from a set of possible notification types based on at least a portion of the original message; and selecting one or more property values from one or more respective ranges of possible property values. The selected notification type and selected property value(s) define a recipient-instantiated (RI) notification. The technique then displays the RI notification on a user interface presentation of a recipient-user computing device. In one approach, the technique can randomly select the notification type and/or the property value(s). In addition, or alternatively, the technique can make these choices based on context information.