Hi Anthony,
The logic in your comments looks perfect.
1) Move messages to message_read when user is deleted.
2) Move them back to message when user is "revived" (knowing that right now, that "reviving" option isn't possible at all because of the lost username problem.
I'd add one more step:
3) Add one upgrade step in order to perform the (1) move sitewide.
I've been looking to your proposed patches. And they look 99% fine.
In 1) you are storing those messages with timeread=0, perfect. Also, any attempt to see a discussion with one deleted user will end with a "user deleted" error message. Perfect too.
In 2) when "reviving" users (although, once more, that's not possible right now), it seems that, when selecting messages to be moved from mesage_read back to message, you are missing one condition, the "and timeread = 0". Else ALL read messages from the user will be moved to message table. And we don't want that IMO.
About 3) it's missing and I think it could be interesting to have it in order to clean current repetitive messages. It's basically 1) but iterating over all deleted users having messages in message table. Can you do that? Or should I try it?
TIA and ciao 
Also related is whether a user should be able to view messages of deleted users. From MoodleHQ chat:
mathieu: what happens to messages received (and read) from a user that's now deleted? can they be accessed?
(10:02:26 PM) mathieu: I suppose we should make both case do the same
(10:03:27 PM) arborrow: I'm not sure, I'd suspect not
(10:06:37 PM) arborrow: actually if you put in the URL for /message/history.php you can get the history as it is using a get_record("user", "id", $userid1)
(10:06:51 PM) arborrow: we could add a check to see if the user has been deleted
(10:07:14 PM) arborrow: and display a message indicating such