SE doesn't delete the characters. They just ban them. When you see (Deleted) it was the account holder themselves who did that. RMT have started deleting their own characters to get around blist. It's up to you to go back and prune the old names from your blist.