In the config file - if you set the option which says " Allow users that are not logged in to choose an unregistered username for their post" to Yes, then the user's name is retained with their posts - otherwise it'll say "Anonymous". It's your choice.
This doesn't help searches. Searches are done on user number, so if you delete the user, all thier posts are assigned to user number 1 - so there's no way to search by username for deleted users. The above is only cosmetic when the posts are displayed.