It appears that deleted users still appear in other user's contact list. Start with two user. User A adds user B as a contact. Delete user B.

When user A visits the message page user B is in their contacts and click on them gives the following:

Invalid user
Debug info: SELECT id FROM

WHERE id = ? AND deleted = ?
[array (
0 => '3',
1 => 0,
)]
Error code: invaliduser
Stack trace:

line 1390 of /lib/dml/moodle_database.php: dml_missing_record_exception thrown
line 1366 of /lib/dml/moodle_database.php: call to moodle_database->get_record_select()
line 6358 of /lib/accesslib.php: call to moodle_database->get_record()
line 2110 of /lib/navigationlib.php: call to context_user::instance()
line 1269 of /lib/navigationlib.php: call to global_navigation->load_for_user()
line 3003 of /lib/navigationlib.php: call to global_navigation->initialise()
line 791 of /lib/pagelib.php: call to navbar->has_items()
line 4 of /theme/base/layout/general.php: call to moodle_page->has_navbar()
line 866 of /lib/outputrenderers.php: call to include()
line 796 of /lib/outputrenderers.php: call to core_renderer->render_page_layout()
line 215 of /message/index.php: call to core_renderer->header()