Check out the bp_get_thread_recipients_list() function:
https://buddypress.trac.wordpress.org/browser/tags/3.1.0/src/bp-messages/bp-messages-template.php?marks=1725-1729#L1711
The Deleted User string is used if the user profile link does not exist. If the user was deleted, then it makes sense that the string would return 'Deleted User'.
If the user still exists, your next step is to figure out why your user profile links are returning empty. Perhaps via a custom code snippet that is filtering the user profile URL?
